Cod sursa(job #356588)

Utilizator ionutz32Ilie Ionut ionutz32 Data 15 octombrie 2009 13:31:44
Problema Lupul Urias si Rau Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.83 kb
var t,a,oi,heap:array[1..100000] of longint;
n,x,l,i,d,aux,j,m: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);
   j:=n;
   for i:=t[n] downto 1 do
       begin
       while t[j]=i do
             begin
             inc(m);
             heap[m]:=a[oi[j]];
             perc(m);
             dec(j);
             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.