Cod sursa(job #236987)

Utilizator DanielGGlodeanu Ioan Daniel DanielG Data 28 decembrie 2008 21:03:04
Problema Deque Scor 20
Compilator fpc Status done
Runda Arhiva educationala Marime 0.49 kb
var v,deque:array[1..5005] of longint;
n,k,i,front,back:longint;
f:text;
sum:int64;
begin
assign(f,'deque.in');reset(f);
readln(f,n,k);
for i:=1 to n do read(f,v[i]);
close(f);
front:=1; back:=0;
for i:=1 to n do
    begin
    while(front<=back) and (v[i]<=v[deque[back]]) do dec(back);
    inc(back);
    deque[back]:=i;
    if (deque[front]=i-k) then inc(front);
    if (i>=k) then sum:=sum+v[deque[front]];
    end;
assign(f,'deque.out');rewrite(f);
writeln(f,sum);
close(f);
end.