Cod sursa(job #774002)

Utilizator hiepsieunhanhiepsieunhan hiepsieunhan Data 3 august 2012 10:44:08
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.31 kb
Const
        tfi     =       'branza.in';
        tfo     =       'branza.out';
type
        arr1    =       array[1..100000] of longint;
        arr2    =       array[1..100000] of int64;
var
        fi,fo   :       text;
        n,s,t,f,r:       longint ;
        st,c,p  :       arr1 ;
        a       :       arr2 ;
        res     :       int64 ;
        i       :       longint;
BEGIN
        assign(fi,tfi);reset(fi);
        assign(fo,tfo);rewrite(fo);
                  Read(fi,n,s,t);
	          read(fi,c[1],p[1]);
	          a[1]:=c[1]-s;
                  res:=c[1]*p[1];
                  for i:=2 to n do
                    begin
                           Read(fi,c[i],p[i]);
                           a[i]:=c[i]-s*i;
                           res:=res+p[i]*s*i;
                    end;
                  f:=1;
                  r:=1;
                  st[1]:=1;
                  for i:=2 to n do
                    begin
                           while (f<=r) and (a[i]<a[st[r]]) do dec(r);
                           inc(r);
                           st[r]:=i;
                           If (f<=r) and (i-st[f]>t) then inc(f);
                           res:=res+p[i]*a[st[f]];
                    end;
	          write(fo,res);
        close(fo);
        close(fi);
END.