ac1265.pas

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

{$Q-,R-}
program tju1265;
const
  maxn=10000;
var
  time,factor:array[0..maxn]of longint;
  cost:array[0..maxn]of qword;
  q:array[0..maxn]of word;
  n,s,i,f,r:longint;
function slope(a,b:word):real;
  begin
    slope:=(cost[a]-cost[b])/(time[a]-time[b]);
  end;
begin
  repeat
    read(n,s);
    for i:=0 to n-1 do
      read(time[i],factor[i]);
    for i:=n-2 downto 0 do begin
      inc(time[i],time[i+1]);
      inc(factor[i],factor[i+1]);
    end;

    cost[n]:=0;f:=0;r:=-1;
    for i:=n-1 downto 0 do begin
      while (r>f) and (slope(i+1,q[r])<slope(q[r],q[r-1])) do dec(r);
      inc(r);q[r]:=i+1;
      while (r>f) and (slope(q[f+1],q[f])<factor[i]) do inc(f);
      cost[i]:=cost[q[f]]+qword(s+time[i]-time[q[f]])*factor[i];
    end;
    writeln(cost[0]);
  until seekeof;
end.