Cod sursa(job #773126)

Utilizator hiepsieunhanhiepsieunhan hiepsieunhan Data 1 august 2012 03:50:59
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.29 kb
const
        tfi     =       'branza.inp';
        tfo     =       'branza.out';
        Nmax    =       100001;
type
        arr1    =       array[0..Nmax] of longint ;
var
        fi,fo   :       text;
        n,s,t,top1,top     :       longint ;
        st       :       arr1 ;
        c,p      :       array[0..Nmax] of int64 ;
        res     :    int64 ;
procedure Nhap;
var
        i,j,k :longint;
begin
        REad(fi,n,s,t);
        for i := 1 to n do Read(fi,c[i],p[i]) ;
end;
procedure xuly;
var
        i,j,k: longint;
begin
        top1 := 1 ;
        top := 1 ;
        st[1] := 1;
        res := c[1] * p[1] ;
        for i := 2 to n do
          begin
                while (top1 <= top) and (i - st[top1] + 1 > t) do inc(top1) ;
                while (top1 <= top) and (c[i] - s * i <= c[st[top]] - s * st[top]) do dec(top);
                inc(top);
                st[top] := i ;
                res := res + (c[st[top1]] - st[top1] * s + i * s) * p[i] ;
          end;
end;
procedure inkq;
var
        i,j,k: longint;
begin
        write(fo,res);
end;
begin
        assign(fi,tfi);reset(fi);
        assign(fo,tfo);rewrite(fo);
                  Nhap;
                  xuly;
                  inkq;
        close(fo);
        close(fi);
end.