比赛 |
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.