Cod sursa(job #323944)

Utilizator marius21Petcu Marius marius21 Data 14 iunie 2009 11:10:40
Problema Deque Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.8 kb
const FIRST:int64=-100;
const LAST:int64=100;

type deque=object
        private
        a:array[-100..100] 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;

begin
assign(f,'deque.in');
assign(g,'deque.out');
reset(f);
rewrite(g);
d.Init(0);
read(f,n,k);
read(f,a[1]);
d.push_back(1);
s:=0;
for i:=2 to n do begin
        read(f,a[i]);
        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.