Cod sursa(job #32122)

Utilizator VmanDuta Vlad Vman Data 17 martie 2007 12:33:34
Problema Lupul Urias si Rau Scor 24
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.79 kb
program lupu;
const nmax=100001;
var st,i,j,n,x,l,d,max,tmax,nrh,pivot,aux,liber:longint;
    t,a,nr,heap,loc:array[1..nmax]of longint;
    f:text;

procedure qsort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := t[nr[(l+r) DIV 2]];
  repeat
    while t[nr[i]] > x do i := i + 1;
    while x > t[nr[j]] do j := j - 1;
    if i <= j then
    begin
      y := nr[i]; nr[i] := nr[j]; nr[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then qsort(l, j);
  if i < r then qsort(i, r);
end;


begin
assign(f,'lupu.in');reset(f);
readln(f,n,x,l);
for i:=1 to n do begin
    readln(f,d,a[i]);
    if (x-d>=0) then t[i]:=(x-d)div l+1;
    nr[i]:=i;
    if t[i]>tmax then tmax:=t[i];
end;
close(f);
qsort(1,n);
st:=1;
for i:=tmax downto 1 do begin
    while t[nr[st]]=i do
          begin
          if (liber=0) then begin
          inc(nrh);
          heap[nrh]:=nr[st];
          pivot:=nrh;
          end
          else begin heap[loc[liber]]:=nr[st];pivot:=loc[liber];dec(liber);end;
          while (pivot>1)and(a[heap[pivot div 2]]<a[heap[pivot]]) do
                begin
                aux:=heap[pivot];
                heap[pivot]:=heap[pivot div 2];
                heap[pivot div 2]:=aux;
                pivot:=pivot div 2;
                end;
          inc(st);
          end;
   if (nrh>=1) then begin
      inc(max,a[heap[1]]);
      pivot:=1;
      while pivot*2<nrh do begin
          if (a[heap[pivot*2]]>a[heap[pivot*2+1]])
             then begin heap[pivot]:=heap[pivot*2];pivot:=pivot*2;end
                  else begin heap[pivot]:=heap[pivot*2+1];pivot:=pivot*2+1;end;
     end;
     inc(liber);
     loc[liber]:=pivot;
     end;
end;
assign(f,'lupu.out');rewrite(f);
write(f,max);
close(f);
end.