比赛 |
20100913 |
评测结果 |
AAAAAAAAAA |
题目名称 |
越狱 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2010-09-13 21:35:46 |
显示代码纯文本
program prisonbreak(input,output);
var
i,j,n,l,p,t:longint;
oil:array[0..10000,1..2]of longint;
dym:array[0..10000]of longint;
function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;
procedure swap(i,j:longint);
var
t1,t2:longint;
begin
t1:=oil[i,1];
t2:=oil[i,2];
oil[i]:=oil[j];
oil[j,1]:=t1;
oil[j,2]:=t2;
end;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=oil[(l+r) div 2,1];
repeat
while oil[i,1]<x do
inc(i);
while x<oil[j,1] do
dec(j);
if not(i>j) then
begin
swap(i,j);
inc(i);
dec(j);
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(oil[i,1],oil[i,2]);
readln(l,p);
for i:=1 to n do
oil[i,1]:=l-oil[i,1];
sort(1,n);
dym[0]:=p;
for i:=1 to n do
for j:=i downto 1 do
if dym[j-1]>=oil[i,1] then
dym[j]:=max(dym[j-1]+oil[i,2],dym[j]);
for i:=0 to n do
if dym[i]>=l then
begin
writeln(i);
n:=-1;
break;
end;
if n>-1 then
writeln(-1);
close(input);
close(output);
end.