比赛 20100913 评测结果 AWWWWWTTTW
题目名称 越狱 最终得分 10
用户昵称 Achilles 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 21:28:26
显示代码纯文本
program prisonbreak;
var
  sz:array[0..10050,1..2]of longint;
  oil,t,t2:array[0..10050]of longint;
  n,i,j,temp,temp2,min:longint;
procedure qsort(a,b:longint);
var
  p1,p2:longint;
begin
  p1:=a;
  p2:=b;
  if a<b then begin
    while p1<p2 do
    begin
      while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
        p2:=p2-1;
      sz[0]:=sz[p1];
      sz[p1]:=sz[p2];
      sz[p2]:=sz[0];
      while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
        p1:=p1+1;
      sz[0]:=sz[p1];
      sz[p1]:=sz[p2];
      sz[p2]:=sz[0];
    end;
    qsort(a,p1-1);
    qsort(p1+1,b);
  end;
end;
begin
  assign(input,'prisonbreak.in');
  assign(output,'prisonbreak.out');
  reset(input);
  rewrite(output);
  readln(n);
  n:=n+1;
  for i:=1 to n do
    readln(sz[i,1],sz[i,2]);
  qsort(1,n);
  n:=n+1;
  for i:=0 to n do
    oil[i]:=-2000000000;
  oil[0]:=sz[1,2];
  for i:=2 to n do
  begin
    temp:=sz[i-1,1]-sz[i,1];
    for j:=0 to n do
      if oil[j]>0 then begin
        if oil[j]>=temp then
        begin
          t[j]:=oil[j]-temp;
        end
        else t[j]:=-2000000000;
      end
      else t[j]:=-2000000000;
    temp2:=temp;
    temp:=temp-sz[i,2];
    t2[0]:=-2000000000;
    for j:=0 to n-1 do
      if oil[j]>0 then
      begin
        if temp2<=oil[j] then begin
          t2[j+1]:=oil[j]-temp;
        end
        else t2[j+1]:=2000000000;
      end
      else t2[j+1]:=-2000000000;
    for j:=0 to n do
      if t[j]>t2[j] then oil[j]:=t[j] else oil[j]:=t2[j];

  end;
  min:=0;
  for i:=0 to n do
    if oil[i]>=0 then begin
      writeln(i);
      min:=1;
      break;
    end;
  if min=0 then writeln(-1);
  close(input);
  close(output);
end.