比赛 20100913 评测结果 AATTTTEEEW
题目名称 越狱 最终得分 20
用户昵称 ybh 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 22:02:27
显示代码纯文本
program prisonbreak;
var
  a,b:array[0..10000] of longint;
  f:array[0..5001,0..5001] of longint;
  n,i,j,k,m,ans:longint;

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

begin
  assign(input,'prisonbreak.in');
  reset(input);
  assign(output,'prisonbreak.out');
  rewrite(output);

  readln(n);
  for i:=1 to n do
    readln(a[i],b[i]);
  readln(a[0],b[0]);
  m:=a[0];
  for i:=0 to n do
    a[i]:=m-a[i];

  sort(1,n);

  ans:=n;
  f[0,0]:=b[0];
  for i:=1 to n do
    if a[i]<=b[0]
      then f[i,0]:=b[0]-a[i]
      else break;
  if f[n,0]>0 then
  begin
    writeln(0);
    close(input);
    close(output);
    halt
  end;
  for i:=1 to n do
  begin
    for j:=1 to n do
    begin
      for k:=j to i do
      begin
        if (f[k-1,j-1]+b[k]>a[i]) and (f[k-1,j-1]+b[k]>f[i,j]) then
        begin
          f[i,j]:=f[k-1,j-1]+b[k];
          if (f[i,j]>=m) and (j<ans)
            then ans:=j;
        end
      end
    end
  end;

  writeln(ans);
  close(input);
  close(output);
end.