记录编号 |
18935 |
评测结果 |
AAAAAAAAAA |
题目名称 |
越狱 |
最终得分 |
100 |
用户昵称 |
belong.zmx |
是否通过 |
通过 |
代码语言 |
Pascal |
运行时间 |
2.528 s |
提交时间 |
2010-09-24 18:07:14 |
内存使用 |
0.23 MiB |
显示代码纯文本
program prisonbreak1(input,output);
var
a:array[1..10000,1..2]of longint;
i,j:longint;
f:array[0..10000]of longint;
n:longint;
l,p:longint;
flag:boolean;
procedure sort(l,r:longint);
var
i,j,mid,p:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r) div 2,1];
repeat
while a[i,1]< mid do inc(i);
while mid< a[j,1] do dec(j);
if i<=j then
begin
p:=a[i,1];
a[i,1]:=a[j,1];
a[j,1]:=p;
p:=a[i,2];
a[i,2]:=a[j,2];
a[j,2]:=p;
inc(i);
dec(j);
end;
until i >j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
begin
assign(input,'prisonbreak.in');
reset(input);
readln(n);
for i:=1 to n do readln(a[i,1],a[i,2]);
readln(l,p);
close(input);
for i:=1 to n do a[i,1]:=l-a[i,1];
sort(1,n);
f[0]:=p;
for i:=1 to n do
for j:=i downto 1 do
begin
if f[j-1]>=a[i,1] then
f[j]:=max(f[j],f[j-1]+a[i,2]);
end;
assign(output,'prisonbreak.out');
rewrite(output);
for j:=0 to n do
if (f[j]>=l) then
begin
writeln(j);
flag:=true;
break;
end;
if flag=false then writeln('-1');
close(output);
end.