Cod sursa(job #68533)

Utilizator VmanDuta Vlad Vman Data 28 iunie 2007 12:29:34
Problema Branza Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.77 kb
program branza;
const Nmax=100000;
var n,t,s,i,st,dr:longint;
    c,p:array[1..Nmax]of int64;
    l:array[1..Nmax]of longint;
    f:text;
    min:int64;
begin
assign(f,'branza.in');reset(f);
readln(f,n,s,t);
for i:=1 to n do
        readln(f,c[i],p[i]);
min:=c[1]*p[1];
st:=1;
dr:=1;
l[1]:=1;
for i:=2 to t do begin
        while (dr>=st)and(c[i]<=c[l[dr]]+s*(i-l[dr])) do dec(dr);
        inc(dr);
        l[dr]:=i;
        min:=min+(c[l[st]]+s*(i-l[st]))*p[i];
end;
for i:=t+1 to n do begin
        while l[st]<i-t do inc(st);
        while (dr>=st)and(c[i]<=c[l[dr]]+s*(i-l[dr])) do dec(dr);
        inc(dr);
        l[dr]:=i;
        min:=min+(c[l[st]]+s*(i-l[st]))*p[i];
end;
assign(f,'branza.out');rewrite(f);
write(f,min);
close(f);
end.