比赛 |
NOIP2008集训模拟5 |
评测结果 |
AWWWWAWWAA |
题目名称 |
越狱 |
最终得分 |
40 |
用户昵称 |
elysian |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-14 09:40:23 |
显示代码纯文本
program elysian;
const
fin='prisonbreak.in';fout='prisonbreak.out';
var
f,p:array[0..10005,0..1] of longint;
d,a:array[0..10005] of longint;
f1,f2:text;
n,pi:longint;
procedure print;
begin
writeln(f2,-1);
close(f2);
halt;
end;
procedure print0;
begin
writeln(f2,0);
close(f2);
halt;
end;
procedure init;
var
i,j,t1,t2,all:longint;
begin
assign(f1,fin);reset(f1);
assign(f2,fout);rewrite(f2);
readln(f1,n);
all:=0;
d[n+1]:=0;a[n+1]:=0;
for i:=n downto 1 do
begin
readln(f1,d[i],a[i]);
inc(all,a[i]);
end;
readln(f1,d[0],pi);
close(f1);
if all+pi<d[0] then print;
if pi>=d[0] then print0;
filldword(f,sizeof(f) div 4,maxlongint);
filldword(p,sizeof(p) div 4,maxlongint);
f[0,1]:=0;f[0,0]:=0;
p[0,1]:=pi;p[0,0]:=pi;
end;
procedure main;
var
i,k:longint;
begin
for i:=1 to n+1 do
for k:=i-1 downto 0 do
begin
if p[k,0]>=d[k]-d[i] then
if f[k,0]<f[i,0] then {上一次不加油}
begin
f[i,0]:=f[k,0];
p[i,0]:=p[k,0]-(d[k]-d[i]);
end;
if p[k,1]>=d[k]-d[i] then
if f[k,1]<f[i,0] then {上一次加油}
begin
f[i,0]:=f[k,1];
p[i,0]:=p[k,1]-(d[k]-d[i]);
end;
{此次不加油}
if p[k,0]>=d[k]-d[i] then {上一次不加油}
if f[k,0]<>maxlongint then
if f[k,0]+1<f[i,1] then
begin
f[i,1]:=f[k,0]+1;
p[i,1]:=p[k,0]-(d[k]-d[i])+a[i];
end;
if p[k,1]>=d[k]-d[i] then {上一次加油}
if f[k,1]<>maxlongint then
if f[k,1]+1<f[i,1] then
begin
f[i,1]:=f[k,1]+1;
p[i,1]:=p[k,1]-(d[k]-d[i])+a[i];
end;
{此次加油}
if (f[i,1]=maxlongint) and (f[i,0]=maxlongint) then print;
end;
writeln(f2,f[n+1,0]);
close(f2);
end;
begin
init;
main;
end.