Cod sursa(job #774033)

Utilizator hiepsieunhanhiepsieunhan hiepsieunhan Data 3 august 2012 11:17:16
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.85 kb
CONST
        tfi     =       'branza.in';
        tfo     =       'branza.out';
        nmax    =       100100;
TYPE
        arr1 = array [0..nmax] of int64;
VAR
        fi,fo:text;
        n,s,t,f,r:longint;
        res:int64;
        c,p,g,q:arr1;
{________________________________________}
procedure nhap;
var i:longint;
        Begin
                assign(fi,tfi);reset(fi);
                read(fi,n,s,t);
                for i:=1 to n do read(fi,c[i],p[i]);
                close(fi);
        End;
{________________________________________}
procedure push(x:longint);
        Begin
                inc(r);
                q[r]:=x;
        End;
{________________________________________}
procedure xuli;
var i,j,cp:longint;
        Begin
                res:=c[1]*p[1];
                f:=1;
                r:=0;
                push(1);
                for i:=2 to n do
                begin
                        cp:=c[i]*p[i];
                        if cp>c[q[r]]*p[i]+(i-q[r])*s*p[i] then push(i);
                        if f<=r then
                        begin
                                j:=r;
                                while (j>0) and (j>=f) and (cp<=c[q[j]]*p[i]+(i-q[j])*s*p[i]) do
                                begin
                                        q[j]:=i;
                                        r:=j;
                                        dec(j);
                                end;
                                while (f<r) and (q[f]<i-t+1) do inc(f);
                                res:=res+c[q[f]]*p[i]+(i-q[f])*s*p[i];
                        end;
                end;
        End;
{________________________________________}
BEGIN
        assign(fo,tfo);rewrite(fo);
        nhap;
        xuli;
        write(fo,res);
        close(fo);
END.