Cod sursa(job #346468)

Utilizator ionutz32Ilie Ionut ionutz32 Data 7 septembrie 2009 22:05:06
Problema Deque Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.54 kb
var bufin:array[1..65535] of byte;
a,dq:array[1..5000000] of longint;
n,k,i,lo,hi:longint;
s:int64;
f,g:text;
begin
assign(f,'deque.in');
assign(g,'deque.out');
reset(f);rewrite(g);
settextbuf(f,bufin);
readln(f,n,k);
lo:=1;
for i:=1 to n do
    begin
    readln(f,a[i]);
    while (lo<=hi) and (a[dq[hi]]>=a[i]) do
          dec(hi);
    inc(hi);
    dq[hi]:=i;
    if i>=k then
       begin
       while dq[lo]<=i-k do
             inc(lo);
       inc(s,a[dq[lo]]);
       end;
    end;
write(g,s);
close(f);close(g);
end.