比赛 |
20120723 |
评测结果 |
WAWWWWWWWWAWAWWWWWAA |
题目名称 |
珍贵的项链 |
最终得分 |
25 |
用户昵称 |
wo shi 刘畅 |
运行时间 |
0.370 s |
代码语言 |
Pascal |
内存使用 |
79.51 MiB |
提交时间 |
2012-07-23 11:01:12 |
显示代码纯文本
const
oo=maxlongint*1000000;
var
n,k,i,j,l:longint;
now,max,limit:int64;
d:array[0..200000,0..11]of int64;
a,s,f,g:Array[0..2000000]of int64;
begin
assign(input,'dividenecklace.in'); reset(input);
assign(output,'dividenecklace.out'); rewrite(output);
readln(n,k,limit);
for i:=1 to n do read(a[i]);
for i:=n+1 to n+n-1 do a[i]:=a[i-n];
n:=n+n-1;
for i:=1 to n do s[i]:=s[i-1]+a[i];
if k=1 then
begin
max:=-oo;
now:=0;
for i:=1 to n do
begin
if now<0 then now:=a[i]
else now:=now+a[i];
if now>max then max:=now;
end;
if max<=limit then writeln('Go To the Hell')
else begin
writeln('New Pluto was born');
writeln(max);
end;
end
else if k=2 then
begin
max:=-oo;
now:=0;
for i:=1 to n do
begin
if now<0 then now:=a[i]
else now:=now+a[i];
if now>max then max:=now;
f[i]:=max;
end;
max:=-oo;
now:=0;
for i:=n downto 1 do
begin
if now<0 then now:=a[i]
else now:=now+a[i];
if now>max then max:=now;
g[i]:=max;
end;
max:=-oo;
for i:=1 to n-1 do
if f[i]+g[i+1]>max then max:=f[i]+g[i+1];
if max<=limit then writeln('Go To the Hell')
else begin
writeln('New Pluto was born');
writeln(max);
end;
end
else begin
if n>=10000 then writeln('Go To the Hell')
else begin
for i:=0 to n do
for j:=1 to k do
d[i,j]:=-oo;
for i:=1 to n do
for j:=1 to k do
begin
d[i,j]:=d[i-1,j];
for l:=1 to i-1 do
if d[l,j-1]+s[i]-s[l]>d[i,j] then
d[i,j]:=d[l,j-1]+s[i]-s[l];
end;
if d[n,k]<=limit then writeln('Go To the Hell')
else begin
writeln('New Pluto was born');
writeln(d[n,k]);
end;
end;
end;
close(input);
close(output);
end.