记录编号 18656 评测结果 AAAAAAAAAA
题目名称 越狱 最终得分 100
用户昵称 Gravatarmaxiem 是否通过 通过
代码语言 Pascal 运行时间 1.903 s
提交时间 2010-09-17 11:10:27 内存使用 0.23 MiB
显示代码纯文本
program prisonbreak;
var
  f,a,b:array [0..10001] of longint;
  n,step,i,j:longint;
procedure quicksort(x,y:integer);
var l,r,sa,sb:longint;
begin
  if x<y then begin
  l:=x;r:=y;
  sa:=a[l];sb:=b[l];
  repeat
    while (l<r) and (a[r]>=sa) do dec(r);
    if l<r then begin
      a[l]:=a[r];
      b[l]:=b[r];
      inc(l);
    end;
    while (l<r) and (a[l]<=sa) do inc(l);
    if l<r then begin
      a[r]:=a[l];
      b[r]:=b[l];
      dec(r);
    end;
  until l=r;
  a[l]:=sa;
  b[l]:=sb;
  quicksort (x,l-1);
  quicksort (l+1,y);
  end;
end;
begin
  fillchar (a,sizeof(a),0);
  fillchar (b,sizeof(b),0);
  fillchar (f,sizeof(f),$FF);
  assign (input,'prisonbreak.in');
  reset (input);
  readln (n);
  for i:=1 to n+1 do readln (a[i],b[i]);
  close (input);
  quicksort (1,n);
  f[0]:=b[n+1];
  assign (output,'prisonbreak.out');
  rewrite (output);
  if b[n+1]>=a[n+1] then begin
    writeln (0);
	close (output);
	halt;
  end;
  for i:=n downto 1 do begin
    for j:=n-i+1 downto 1 do if f[j-1]>a[n+1]-a[i] then begin
      if f[j-1]+b[i]>f[j] then f[j]:=f[j-1]+b[i];
    end;
  end;
  i:=0;
  while (i<=n+1) and (f[i]<a[n+1]) do inc(i);
  if i<=n+1 then writeln (i) else writeln (-1);
  close (output);
end.