Cod sursa(job #1179611)

Utilizator azkabancont-vechi azkaban Data 28 aprilie 2014 22:31:25
Problema Lupul Urias si Rau Scor 8
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.62 kb
program lupulurias;
var H,A : array [1..200005] of longint;
    i,n,x,l,z,b,pivot,p,suma: longint;
    b1,b2 : array[0..1 shl 17] of char;

procedure swap(var x,y : longint);
  var aux : longint;
    begin
       aux:=x;
       x:=y;
       y:=aux;
    end;

procedure coboara(k : longint);
  var fiu : longint;
    begin
         repeat
               fiu:=0;
               if k*2<=n then
                  begin
                       fiu:=k*2;
                       if  (k*2<n) then
                           if (H[k*2+1]>H[k*2]) then fiu:=k*2+1;
                       if H[fiu]<=H[k] then fiu:=0;
                  end;
                  if fiu<>0 then begin
                                       swap(H[k],H[fiu]);
                                       swap(A[k],A[fiu]);
                                       k:=fiu;
                                 end;

         until fiu=0;
   end;

procedure ridica(nod : longint);
     begin
         if (nod>1) and (H[nod]>H[nod div 2]) then begin
                                                     swap(H[nod],H[nod div 2]);
                                                     swap(A[nod],A[nod div 2]);
                                                     ridica(nod div 2);
                                                   end
                                               else
         if (nod>1) and (H[nod]=H[nod div 2]) and (A[nod]>A[nod div 2]) then swap(A[nod],A[nod div 2]);
       end;

procedure inserare(var n : longint; nod1,nod : longint) ;
  begin
      n:=n+1;
      H[n]:=nod;
      A[n]:=nod1;
      ridica(n);
   end;

procedure stergere(var n : longint ; nod : longint);
  begin
    swap(A[nod],A[n]);
    swap(H[nod],H[n]);
    n:=n-1;
    if (nod>1) and (H[nod]>H[nod div 2]) then ridica(nod)
                                         else coboara(nod);
  end;

begin
   assign(input,'lupu.in'); settextbuf(input,b1); reset(input);
   assign(output,'lupu.out'); settextbuf(output,b2); rewrite(output);
   readln(z,x,l); n:=0;
   for i:=1 to z do begin
                          readln(p,b);
                          inserare(n,p,b);
                    end;
   pivot:=x;
   while n>0 do begin
                     if A[1]<=pivot then begin
                                              suma:=suma+H[1];
                                              stergere(n,1);
                                              pivot:=pivot-l;
                                          end
                                    else stergere(n,1);
                         end;
   writeln(suma);

   close(input);
   close(output);
end.