Cod sursa(job #356508)

Utilizator ionutz32Ilie Ionut ionutz32 Data 14 octombrie 2009 23:10:06
Problema Lupul Urias si Rau Scor 32
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.9 kb
var t,a,oi,heap:array[1..100000] of longint;
n,x,l,i,d,aux,j,m,val:longint;
sol:int64;
f,g:text;
function sort2(min,max:longint):longint;
         var piv:longint;
         k:boolean;
         begin
         piv:=t[min+(max-min) shr 1];
         i:=min-1;
         j:=max+1;
         k:=true;
         repeat
               repeat
                     inc(i);
               until t[i]>=piv;
               repeat
                     dec(j);
               until t[j]<=piv;
               if i<j then
                  begin
                  aux:=t[i];
                  t[i]:=t[j];
                  t[j]:=aux;
                  aux:=oi[i];
                  oi[i]:=oi[j];
                  oi[j]:=aux;
                  end
               else
                   begin
                   sort2:=j;
                   k:=false;
                   break;
                   end;
         until k=false;
         end;
procedure sort(min,max:longint);
          var p:longint;
          begin
          if min<max then
             begin
             p:=sort2(min,max);
             sort(min,p);
             sort(p+1,max);
             end;
          end;
procedure perc(poz:longint);
          begin
          while (poz<>1) and (heap[poz]>heap[poz shr 1]) do
                begin
                aux:=heap[poz];
                heap[poz]:=heap[poz shr 1];
                heap[poz shr 1]:=aux;
                poz:=poz shr 1;
                end;
          end;
procedure sift(poz:longint);
          var max:longint;
          begin
          while (poz<=m shr 1) and ((heap[poz*2]>heap[poz]) or (heap[poz*2+1]>heap[poz])) do
                begin
                if heap[poz*2]>heap[poz*2+1] then
                   max:=poz*2
                else
                    max:=poz*2+1;
                aux:=heap[poz];
                heap[poz]:=heap[max];
                heap[max]:=aux;
                poz:=max;
                end;
          end;
begin
assign(f,'lupu.in');
assign(g,'lupu.out');
reset(f);rewrite(g);
readln(f,n,x,l);
if l<>0 then
   begin
   for i:=1 to n do
       begin
       readln(f,d,a[i]);
       oi[i]:=i;
       if d<=x then
          t[i]:=(x-d) div l+1
       end;
   sort(1,n);
   i:=n;
   while (i>0) and (t[i]>0) do
         begin
         val:=t[i];
         while (i>0) and (t[i]=val) do
               begin
               inc(m);
               heap[m]:=a[oi[i]];
               perc(m);
               dec(i);
               end;
         if m>0 then
            begin
            inc(sol,heap[1]);
            heap[1]:=heap[m];
            dec(m);
            sift(1);
            end;
         end;
   write(g,sol);
   end
else
    begin
    for i:=1 to n do
        begin
        readln(f,d,aux);
        if d<=x then
           inc(sol,aux);
        end;
    write(g,sol);
    end;
close(f);close(g);
end.