记录编号 |
18656 |
评测结果 |
AAAAAAAAAA |
题目名称 |
越狱 |
最终得分 |
100 |
用户昵称 |
maxiem |
是否通过 |
通过 |
代码语言 |
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.