Cod sursa(job #72743)

Utilizator vanila0406Ionescu Victor vanila0406 Data 15 iulie 2007 12:58:39
Problema Lupul Urias si Rau Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.5 kb
program lupu;
type oaie=record
        d,l:longint;
end;
var f,g:text;
        n,x,d,dim:longint;
        v:array[1..100001] of oaie;
        nr,b:array[1..100001] of longint;



procedure iofile;
var i:longint;
begin
        assign(f,'lupu.in');reset(f);
        assign(g,'lupu.out');rewrite(g);
        readln(f,n,d,x);
        dim:=n;
        for i:=1 to n do
                readln(f,v[i].d,v[i].l);
        close(f);
end;



procedure repair(i:longint);
var l,r,max:longint;
        aux:oaie;
begin
        l:=i*2;
        r:=l+1;
        max:=i;
        if (l<=dim)and((v[l].d<v[i].d)or((v[l].d=v[i].d)and(v[l].l<v[i].l)))
        then max:=l;
        if (r<=dim)and((v[r].d<v[max].d)or((v[r].d=v[max].d)and(v[r].l<
        v[max].l))) then max:=r;
        if max<>i then
                begin
                        aux:=v[i];
                        v[i]:=v[max];
                        v[max]:=aux;
                        repair(max);
                end;
end;


procedure build_heap;
var i:longint;
begin
        for i:=n div 2 downto 1 do
                repair(i);
end;



procedure heapsort;
var i:longint;
        aux:oaie;
begin
        for i:=n downto 2 do
                begin
                        aux:=v[1];
                        v[1]:=v[i];
                        v[i]:=aux;
                        dec(dim);
                        repair(1);
                end;
end;


procedure din;
var i,max,j:longint;
begin
        for i:=1 to n do
                begin
                        if v[i].d>d then
                                begin
                                        b[i]:=0;
                                        nr[i]:=0;
                                end else
                                begin
                                        b[i]:=v[i].l;
                                        nr[i]:=0;
                                end;
                        for j:=1 to i-1 do
                                if (v[i].d+(x*(nr[j])))<=d then
                                if b[i]<b[j]+v[i].l then
                                begin
                                        b[i]:=b[j]+v[i].l;
                                        nr[i]:=nr[j]+1;
                                end;
                end;
        max:=b[1];
        for i:=2 to n do
                if b[i]>max then max:=b[i];
        writeln(g,max);
        close(g);
end;



begin
        iofile;
        heapsort;
        din;
end.