比赛 20090916练习赛 评测结果 AAAAAAAAAA
题目名称 任务安排 最终得分 100
用户昵称 Achilles 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2009-09-16 20:45:51
显示代码纯文本
program batch ;

const
    maxn=5001;
var
    sumT,sumC:array[0 .. maxn] of longint;
    f:array[0..maxn] of longint;
    que:array[0..maxn] of longint;
    n,m:longint ;
procedure init ;
var
    i,a,b:longint ;
begin
    readln(n) ;
    readln(m) ;
    for i:=1 to n do readln(sumT[i],sumC[i]) ;
    sumT[n+1]:=0;
    sumC[n+1] := 0 ;
    for i:=n downto 1 do
    	sumT[i]:=sumT[i+1]+sumT[i] ;
    for i:=n downto 1 do
	sumC[i]:=sumC[i+1]+sumC[i] ;
end;
function sploe(j1,j2:longint):extended ;
begin
    sploe:=(f[j1]-f[j2])/(sumT[j1]-sumT[j2]) ;
end ;
Procedure Dp ;
var
    l,r,i:longint ;
begin
    f[n+1]:=0 ;
    l:=1;
    r:=1;
    que[1]:=n+1 ;
    for i := n downto 1 do
    begin
        while (r>l)and(Sploe(que[l],que[l+1])<=sumC[i]) do
	    l:=l+1;
        f[i]:=f[que[l]]+(m+sumT[i]-sumT[que[l]])*sumC[i] ;
        while (r>l)and(Sploe(que[r-1],que[r])>=sploe(que[r],i)) do
	    r:=r-1;
        r:=r+1;
        que[r]:=i;
    end ;
    writeln(f[1]);
end ;
Begin
    assign(input,'batch.in');
    assign(output,'batch.out');
    reset(input);
    rewrite(output);
    init;
    dp;
    close(input);
    close(output);
end .