Pagini recente » Cod sursa (job #2427365) | Cod sursa (job #3234662) | Cod sursa (job #2998465) | Cod sursa (job #1043827) | Cod sursa (job #323956)
Cod sursa(job #323956)
const FIRST:longint=0;
const LAST:longint=5000000;
type deque=object
private
a:array[0..5000000] 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:longint;
a:array[1..5000000] of longint;
bufin:array[0..2097152] of byte;
s:int64;
sgn:shortint;
c:char;
begin
assign(f,'deque.in');
assign(g,'deque.out');
reset(f);
settextbuf(f,bufin);
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.