Cod sursa(job #774007)

Utilizator hiepsieunhanhiepsieunhan hiepsieunhan Data 3 august 2012 10:53:25
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.51 kb
CONST
        tfi     ='branza.in';
        tfo     ='branza.out';
        nmax    =100000;
TYPE
        arr1    =array [0..nmax] of longint;
VAR
        fi,fo   :text;
        c,p,st  :arr1;
        n,t,s,top,k:longint;
        res     :int64;
 (********************************************************************)
Procedure nhap;
      Var
        i       :longint;
      Begin
        assign(fi,tfi);reset(fi);
          read(fi,n,s,k);
          for i:=1 to n do read(fi,c[i],p[i]);
        close(fi);
      End;
 (********************************************************************)
Procedure push(x:longint);
      Begin
        inc(top);
        st[top]:=x;
      End;
 (********************************************************************)
Procedure lam;
      Var
        i,t     :longint;
      Begin
        push(1);
        res:=int64(c[1])*p[1];
        t:=1;
        for i:=2 to n do
          begin
            if i-st[t]>=k then inc(t);
            while (top>=t) and (c[st[top]]-s*st[top]>=c[i]-s*i) do dec(top);
            push(i);
            res:=res+int64(s)*int64(p[i])*(int64(i)-int64(st[t]))+int64(c[st[t]])*int64(p[i]);
          end;
      End;
 (********************************************************************)
Procedure inkq;
      Begin
        assign(fo,tfo);rewrite(fo);
          write(fo,res);
        close(fo);
      End;
 (*********************************************************************)
BEGIN
        nhap;
        lam;
        inkq;
END.