比赛 |
20100913 |
评测结果 |
AWWWWWTTTW |
题目名称 |
越狱 |
最终得分 |
10 |
用户昵称 |
Achilles |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2010-09-13 21:28:26 |
显示代码纯文本
program prisonbreak;
var
sz:array[0..10050,1..2]of longint;
oil,t,t2:array[0..10050]of longint;
n,i,j,temp,temp2,min:longint;
procedure qsort(a,b:longint);
var
p1,p2:longint;
begin
p1:=a;
p2:=b;
if a<b then begin
while p1<p2 do
begin
while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
p2:=p2-1;
sz[0]:=sz[p1];
sz[p1]:=sz[p2];
sz[p2]:=sz[0];
while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
p1:=p1+1;
sz[0]:=sz[p1];
sz[p1]:=sz[p2];
sz[p2]:=sz[0];
end;
qsort(a,p1-1);
qsort(p1+1,b);
end;
end;
begin
assign(input,'prisonbreak.in');
assign(output,'prisonbreak.out');
reset(input);
rewrite(output);
readln(n);
n:=n+1;
for i:=1 to n do
readln(sz[i,1],sz[i,2]);
qsort(1,n);
n:=n+1;
for i:=0 to n do
oil[i]:=-2000000000;
oil[0]:=sz[1,2];
for i:=2 to n do
begin
temp:=sz[i-1,1]-sz[i,1];
for j:=0 to n do
if oil[j]>0 then begin
if oil[j]>=temp then
begin
t[j]:=oil[j]-temp;
end
else t[j]:=-2000000000;
end
else t[j]:=-2000000000;
temp2:=temp;
temp:=temp-sz[i,2];
t2[0]:=-2000000000;
for j:=0 to n-1 do
if oil[j]>0 then
begin
if temp2<=oil[j] then begin
t2[j+1]:=oil[j]-temp;
end
else t2[j+1]:=2000000000;
end
else t2[j+1]:=-2000000000;
for j:=0 to n do
if t[j]>t2[j] then oil[j]:=t[j] else oil[j]:=t2[j];
end;
min:=0;
for i:=0 to n do
if oil[i]>=0 then begin
writeln(i);
min:=1;
break;
end;
if min=0 then writeln(-1);
close(input);
close(output);
end.