Cod sursa(job #32130)

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

procedure qsort(l, r: longint);
var
  i, j, x, y: longint;
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
          inc(nrh);
          heap[nrh]:=nr[st];
          pivot:=nrh;
          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;
     heap[pivot]:=heap[nrh];
     heap[nrh]:=0;
     dec(nrh);
     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;
    end;
end;
assign(f,'lupu.out');rewrite(f);
write(f,max);
close(f);
end.