Pagini recente » Cod sursa (job #2748899) | Cod sursa (job #443714) | Cod sursa (job #303030) | Cod sursa (job #872860) | Cod sursa (job #774033)
Cod sursa(job #774033)
CONST
tfi = 'branza.in';
tfo = 'branza.out';
nmax = 100100;
TYPE
arr1 = array [0..nmax] of int64;
VAR
fi,fo:text;
n,s,t,f,r:longint;
res:int64;
c,p,g,q:arr1;
{________________________________________}
procedure nhap;
var i:longint;
Begin
assign(fi,tfi);reset(fi);
read(fi,n,s,t);
for i:=1 to n do read(fi,c[i],p[i]);
close(fi);
End;
{________________________________________}
procedure push(x:longint);
Begin
inc(r);
q[r]:=x;
End;
{________________________________________}
procedure xuli;
var i,j,cp:longint;
Begin
res:=c[1]*p[1];
f:=1;
r:=0;
push(1);
for i:=2 to n do
begin
cp:=c[i]*p[i];
if cp>c[q[r]]*p[i]+(i-q[r])*s*p[i] then push(i);
if f<=r then
begin
j:=r;
while (j>0) and (j>=f) and (cp<=c[q[j]]*p[i]+(i-q[j])*s*p[i]) do
begin
q[j]:=i;
r:=j;
dec(j);
end;
while (f<r) and (q[f]<i-t+1) do inc(f);
res:=res+c[q[f]]*p[i]+(i-q[f])*s*p[i];
end;
end;
End;
{________________________________________}
BEGIN
assign(fo,tfo);rewrite(fo);
nhap;
xuli;
write(fo,res);
close(fo);
END.