Cod sursa(job #323988)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 14 iunie 2009 12:23:35
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.67 kb
var c,deque,p:array[1..100000] of int64;
    f,g:text;
    s,t,n,i,back,front:longint;
    suma:qword;

begin
 assign(f,'branza.in'); reset(f);
 assign(g,'branza.out'); rewrite(g);
 read(f,n,s,t);
 for i:=1 to n do
        read(f,c[i],p[i]);
 front:=1; back:=0; suma:=0;
 for i:=1 to n do begin
        while (front<=back) and (c[i]<=c[deque[back]]+(i-deque[back])*s) do
                back:=back-1;
        back:=back+1;
        deque[back]:=i;
        if (deque[front]=i-t) then
                front:=front+1;
        aux:=c[deque[front]]+(i-deque[front])*s;
        aux:=aux*p[i];
        suma:=suma+aux;
 end;
 writeln(g,suma);
 close(f); close(g);
end.