Cod sursa(job #31813)

Utilizator floringh06Florin Ghesu floringh06 Data 16 martie 2007 16:18:15
Problema Lupul Urias si Rau Scor 8
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.43 kb
type sheep = record d,cat:longint; end;

var fi,fo:text;
    i,j,n,x,l,max,min,ind,sum:longint;
    c:array[1..100000] of sheep;

 procedure part(st,dr:longint; var stst,stdr,drst,drdr:longint);
   var piv,i,j:longint;
       aux:sheep;
   begin
    piv:=c[(st+dr) div 2].cat;
    i:=st-1;
    j:=dr+1;
    while i<j do
     begin
      repeat inc(i) until c[i].cat<=piv;
      repeat dec(j) until c[j].cat>=piv;
      if i<j then
       begin
        aux:=c[i];
        c[i]:=c[j];
        c[j]:=aux;
       end;
     end;
    stst:=st; drdr:=dr;
    if i=j then begin stdr:=j-1; drst:=i+1; end
     else
    begin stdr:=j; drst:=i; end;
   end;

 procedure sort(st,dr:longint);
  var stst,stdr,drst,drdr:longint;
   begin
   if st<dr then begin
    part(st,dr,stst,stdr,drst,drdr);
    sort(stst,stdr);
    sort(drst,drdr);
    end;
   end;



begin
 assign(fi,'lupu.in'); reset(fi);
 assign(fo,'lupu.out'); rewrite(fo);
 readln(fi,n,x,l);
 for i:=1 to n do
  readln(fi,c[i].d,c[i].cat);
 sort(1,n);
 min:=1000000;
 sum:=0;
 for i:=1 to n do
  if c[i].d<min then min:=c[i].d;
 while x>=min do
  begin
   max:=0;
   for i:=1 to n do
    if c[i].d<=x then
     if c[i].cat>max then
      begin
       max:=c[i].cat;
       ind:=i;
      end;
   c[ind].cat:=0;
   inc(sum,max);
   dec(x,l);
  end;
{ for i:=1 to n do
  writeln(fo,c[i].d,' ',c[i].cat);}
writeln(fo,sum);
close(fi);
close(fo);
end.