Cod sursa(job #773995)

Utilizator hiepsieunhanhiepsieunhan hiepsieunhan Data 3 august 2012 10:35:16
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.95 kb
CONST
        tfi     ='branza.in';
        tfo     ='branza.out';
        nmax    =100000;
TYPE
        arr     =array [0..nmax] of longint;
        arr1    =array [0..nmax] of int64;
VAR
        fi,fo   :text;
        c,p,st  :arr;
        g,h,f   :arr1;
        n,t,s,top,k:longint;
 (********************************************************************)
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 khoitao;
      Var
        i       :longint;
      Begin
        g[1]:=p[1];
        for i:=2 to n do g[i]:=g[i-1]+p[i];
        h[1]:=p[1];
        for i:=2 to n do h[i]:=h[i-1]+g[i];
      End;
 (********************************************************************)
Procedure lam;
      Var
        i,t     :longint;
      Begin
        push(1);
        f[1]:=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);
          if i=st[t] then
          f[i]:=f[st[t]-1]+int64(c[st[t]])*p[st[t]]
          else
          f[i]:=f[st[t]]+c[st[t]]*(g[i]-g[st[t]])+s*(-h[i-1]+h[st[t]-1]
          +g[i]*(i-st[t]));
          end;
      End;
 (********************************************************************)
Procedure inkq;
      Begin
        assign(fo,tfo);rewrite(fo);
          write(fo,f[n]);
        close(fo);
      End;
 (*********************************************************************)
BEGIN
        nhap;
        khoitao;
        lam;
        inkq;
END.