比赛 20100913 评测结果 AWWWTATTAA
题目名称 越狱 最终得分 40
用户昵称 donny 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 21:39:47
显示代码纯文本
program prisonbreak(input,output);
type
  s=record
    lu:array[0..5001]of integer;
  end;
var
  n,i,j,k,m,x,y:longint;
  l,p:array[1..10001]of longint;
  a:array[1..10001,1..2]of longint;
  b:array[1..10001]of s;
begin
  assign(input,'prisonbreak.in');
  reset(input);
  assign(output,'prisonbreak.out');
  rewrite(output);
  readln(n);
  for i:=n downto 1 do
    readln(l[i],p[i]);
  for i:=1 to n do
    for j:=i+1 to n-1 do
    if l[j]<l[j+1] then
    begin
      k:=l[j];
      l[j]:=l[j+1];
      l[j+1]:=k;
      k:=p[j];
      p[j]:=p[j+1];
      p[j+1]:=k;
    end;
  readln(x,y);
  a[1,2]:=y-(x-l[1]);
  l[n+1]:=0;
  p[n+1]:=0;
  if a[1,2]<0 then
  begin
    writeln('-1');
    close(input);
    close(output);
    halt;
  end;
  a[1,1]:=0;
  for i:=1 to n do
    b[i].lu[0]:=0;
  k:=p[1]+a[1,2];
  for i:=2 to n do
    if k>=l[1]-l[i] then
    begin
      if b[i].lu[0]<500 then
      begin
        inc(b[i].lu[0]);
        b[i].lu[b[i].lu[0]]:=1;
      end
      else
      begin
        b[i].lu[501]:=1;
        for j:=1 to n do
          b[i].lu[j]:=b[i].lu[j+1];
      end;
    end
    else break;
  for i:=2 to n+1 do
  begin
    a[i,2]:=a[i-1,2]-l[i-1]+l[i];
    if a[i,2]<0 then
    begin
      k:=0;
      for j:=1 to b[i].lu[0] do
        if p[b[i].lu[j]]>k then
          k:=p[b[i].lu[j]];
      a[i,2]:=a[i,2]+k;
      if a[i,2]<0 then
      begin
        writeln('-1');
        close(input);
        close(output);
        halt;
      end;
      a[i,1]:=a[i-1,1]+1;
    end
    else
    a[i,1]:=a[i-1,1];
    if i<>n+1 then
    begin
    k:=p[i]+a[i,2];
    for j:=i+1 to n do
      if k>=l[i]-l[j] then
      begin
        if b[j].lu[0]<500 then
        begin
          inc(b[j].lu[0]);
          b[j].lu[b[j].lu[0]]:=i;
        end
        else
        begin
          b[j].lu[501]:=i;
          for m:=1 to n do
            b[j].lu[m]:=b[j].lu[m+1];
        end;
      end
      else break;
    end;
  end;
  writeln(a[n+1,1]);
  close(input);
  close(output);
end.