Pagini recente » Cod sursa (job #2556194) | Cod sursa (job #2402411) | Cod sursa (job #2622887) | Cod sursa (job #923270) | Cod sursa (job #323952)
Cod sursa(job #323952)
const FIRST:int64=-5000000;
const LAST:int64=5000000;
type deque=object
private
a:array[-5000000..5000000] of int64;
p,u:int64;
public
procedure init(e:int64);
function pop_back:int64;
function pop_front:int64;
function empty:boolean;
procedure push_front(e:int64);
procedure push_back(e:int64);
function front:int64;
function back:int64;
end;
procedure deque.init(e:int64);
begin
p:=e;
u:=e-1;
end;
function deque.empty:boolean;
begin
empty:=p>u;
end;
function deque.front:int64;
begin
if not empty then
front:=a[p];
end;
function deque.back:int64;
begin
if not empty then
back:=a[u];
end;
function deque.pop_front:int64;
begin
if not empty then begin
pop_front:=a[p];
inc(p);
end;
end;
function deque.pop_back:int64;
begin
if not empty then begin
pop_back:=a[u];
dec(u);
end;
end;
procedure deque.push_front(e:int64);
begin
if p<>FIRST then begin
dec(p);
a[p]:=e;
end;
end;
procedure deque.push_back(e:int64);
begin
if u<>LAST then begin
inc(u);
a[u]:=e;
end;
end;
var f,g:text;
d:deque;
n,k,i:longint;
a:array[1..5000000] of int64;
s:int64;
sgn:shortint;
c:char;
begin
assign(f,'deque.in');
assign(g,'deque.out');
reset(f);
rewrite(g);
d.Init(0);
read(f,n,k);
readln(f,a[1]);
d.push_back(1);
s:=0;
for i:=2 to n do begin
//read(f,a[i]);
sgn:=1;
read(f,c);
if c='-' then begin
sgn:=-1;
read(f,c);
end;
while (c in ['0'..'9']) do begin
a[i]:=a[i]*10+sgn*(ord(c)-ord('0'));
read(f,c);
end;
//readln(f);
if i>k then
if d.front<=i-k then
d.pop_front;
while (not d.empty)and(a[i]<a[d.back]) do
d.pop_back;
d.push_back(i);
if i>=k then
s:=s+a[d.front];
end;
writeln(g,s);
close(f);
close(g);
end.