比赛 20100913 评测结果 AAAAAAAAAA
题目名称 越狱 最终得分 100
用户昵称 belong.zmx 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 21:41:38
显示代码纯文本
program prisonbreak1(input,output);
var
 a:array[1..10000,1..2]of longint;
 i,j:longint;
 f:array[0..10000]of longint;
 n:longint;
 l,p:longint;
 flag:boolean;

procedure sort(l,r:longint);
var
 i,j,mid,p:longint;
begin
 i:=l;
 j:=r;
 mid:=a[(l+r) div 2,1];
 repeat
  while a[i,1]< mid do inc(i);
  while mid< a[j,1] do dec(j);
  if i<=j then
  begin
   p:=a[i,1];
   a[i,1]:=a[j,1];
   a[j,1]:=p;
   p:=a[i,2];
   a[i,2]:=a[j,2];
   a[j,2]:=p;
   inc(i);
   dec(j);
  end;
 until i >j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;

function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;

begin
 assign(input,'prisonbreak.in');
 reset(input);
 readln(n);
 for i:=1 to n do readln(a[i,1],a[i,2]);
 readln(l,p);
 close(input);

 for i:=1 to n do a[i,1]:=l-a[i,1];
 sort(1,n);

 f[0]:=p;
 for i:=1 to n do
  for j:=i downto 1 do
  begin
   if f[j-1]>=a[i,1] then
    f[j]:=max(f[j],f[j-1]+a[i,2]);
  end;

 assign(output,'prisonbreak.out');
 rewrite(output);
 for j:=0 to n do
  if (f[j]>=l) then
  begin
   writeln(j);
   flag:=true;
   break;
  end;
 if flag=false then writeln('-1');
 close(output);
end.