Pagini recente » Cod sursa (job #1939050) | Cod sursa (job #1909462) | Cod sursa (job #3212514) | Cod sursa (job #1351220) | Cod sursa (job #324005)
Cod sursa(job #324005)
const FIRST:longint=0;
const LAST:longint=100000;
type deque=object
private
a:array[0..100000] of longint;
p,u:longint;
public
procedure init(e:longint);
function pop_back:longint;
function pop_front:longint;
function empty:boolean;
procedure push_front(e:longint);
procedure push_back(e:longint);
function front:longint;
function back:longint;
end;
procedure deque.init(e:longint);
begin
p:=e;
u:=e-1;
end;
function deque.empty:boolean;
begin
empty:=p>u;
end;
function deque.front:longint;
begin
if not empty then
front:=a[p];
end;
function deque.back:longint;
begin
if not empty then
back:=a[u];
end;
function deque.pop_front:longint;
begin
if not empty then begin
pop_front:=a[p];
inc(p);
end;
end;
function deque.pop_back:longint;
begin
if not empty then begin
pop_back:=a[u];
dec(u);
end;
end;
procedure deque.push_front(e:longint);
begin
if p<>FIRST then begin
dec(p);
a[p]:=e;
end;
end;
procedure deque.push_back(e:longint);
begin
if u<>LAST then begin
inc(u);
a[u]:=e;
end;
end;
var f,g:text;
d:deque;
n,k,i,h:longint;
c,a:array[1..100000] of longint;
//bufin:array[0..2097152] of byte;
s:int64;
//sgn:shortint;
begin
assign(f,'branza.in');
assign(g,'branza.out');
reset(f);
//settextbuf(f,bufin);
rewrite(g);
d.Init(0);
read(f,n,h,k);
read(f,a[1]);
read(f,c[1]);
s:=a[1]*c[1];
d.push_back(1);
for i:=2 to n do begin
read(f,a[i],c[i]);
if i>k+1 then
if d.front<=i-k-1 then
d.pop_front;
while (not d.empty)and(a[i]<a[d.back]+h*(i-d.back)) do
d.pop_back;
d.push_back(i);
s:=s+(a[d.front]+h*(i-d.front))*c[i];
end;
writeln(g,s);
close(f);
close(g);
end.