Cod sursa(job #324005)

Utilizator marius21Marius Petcu marius21 Data 14 iunie 2009 12:32:08
Problema Branza Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.95 kb
const FIRST:longint=0;
const LAST:longint=100000;

type deque=object
        private
        a:array[0..100000] 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,h:longint;
c,a:array[1..100000] of longint;
//bufin:array[0..2097152] of byte;
s:int64;
//sgn:shortint;

begin

assign(f,'branza.in');
assign(g,'branza.out');
reset(f);
//settextbuf(f,bufin);
rewrite(g);
d.Init(0);
read(f,n,h,k);
read(f,a[1]);
read(f,c[1]);
s:=a[1]*c[1];
d.push_back(1);
for i:=2 to n do begin
        read(f,a[i],c[i]);
        if i>k+1 then
                if d.front<=i-k-1 then
                        d.pop_front;
        while (not d.empty)and(a[i]<a[d.back]+h*(i-d.back)) do
                d.pop_back;
        d.push_back(i);
        s:=s+(a[d.front]+h*(i-d.front))*c[i];
        end;
writeln(g,s);
close(f);
close(g);
end.