Pagini recente » Cod sursa (job #191452) | Cod sursa (job #826445) | Cod sursa (job #1319332) | Cod sursa (job #783960) | Cod sursa (job #773995)
Cod sursa(job #773995)
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.