比赛 20100913 评测结果 AWWWAATTTW
题目名称 越狱 最终得分 30
用户昵称 wo shi 刘畅 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 21:20:45
显示代码纯文本
var
  n,i,l,p,j:longint;
  a,b:array[-1..10001]of longint;
  f:Array[-1..10001,-1..1000]of longint;

function max(x,y:longint):longint;
begin
  if x>y then exit(x);
  exit(y);
end;

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 i := i + 1;
    while x > a[j] do j := j - 1;
    if 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

  begin

    readln(a[n-i+1],b[n-i+1]);

  end;

  readln(l,p);

  sort(1,n);

  f[0,0]:=p;

  a[0]:=l;

  for i:=1 to n do

  begin

    for j:=0 to i do

    begin

      f[i,j]:=-1;

      if (j>0)and(f[i-1,j-1]+b[i]-a[i-1]+a[i]>f[i,j]) then

      f[i,j]:=f[i-1,j-1]+b[i]-a[i-1]+a[i];

      if f[i-1,j]-a[i-1]+a[i]>f[i,j] then

      f[i,j]:=f[i-1,j]-a[i-1]+a[i];

    end;

  end;

  for i:=0 to n do

  if f[n,i]>=a[n] then
  begin

    writeln(i);

    close(input);

    close(output);

    halt;

  end;

  writeln(-1);

  close(input);

  close(output);

end.