ac1171.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 33 行

program tju1171;
const
  maxn=10000;
var
  s,f:array[0..maxn+1]of int64;
  q:array[1..maxn]of word;
  n,t,i,j,front,rear:longint;
function g(a,b:word):real;
  begin
    g:=(f[b]-f[a])/(s[a]-s[b]);
  end;
begin
  repeat
    read(n,t);
    for i:=1 to n do begin
      read(j);
      s[i]:=s[i-1]+j;
    end;
    s[n+1]:=s[n]+1;//Just to make s[n+1] larger than s[n]

    f[n]:=0;front:=1;rear:=0;
    for i:=n-1 downto 0 do begin
      if s[i+1]<s[i+2] then begin
        while (rear>front) and (g(q[rear-1],q[rear])<=g(q[rear],i+1)) do dec(rear);
        inc(rear);q[rear]:=i+1;
      end;
      while (front<rear) and (g(q[front],q[front+1])>i) do inc(front);
      f[i]:=f[q[front]]+(s[q[front]]-s[i])*i-t;
    end;
    writeln(f[0]);
  until seekeof;
end.