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