Cod sursa(job #356460)

Utilizator ionutz32Ilie Ionut ionutz32 Data 14 octombrie 2009 20:33:12
Problema Lupul Urias si Rau Scor 32
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.1 kb
var t,a,oi,heap:array[1..100000] of longint;
n,x,l,i,d,s,t2,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
if l<>0 then
   begin
   s:=x div l;
   if x mod l>0 then
      inc(s);
   end
else
    s:=1;
for i:=1 to n do
    begin
    readln(f,d,a[i]);
    oi[i]:=i;
    if d<=x then
       begin
       if l<>0 then
          t2:=(x-d) div l+1
       else
           t2:=0;
       t[i]:=t2;
       end;
    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
            if t[i]<=x then
               begin
               inc(m);
               heap[m]:=a[oi[i]];
               perc(m);
               end;
            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.