Cod sursa(job #31787)

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

var fi,fo:text;
    i,j,n,x,l,max,maxcat,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].d;
    i:=st-1;
    j:=dr+1;
    while i<j do
     begin
      repeat inc(i) until c[i].d>=piv;
      repeat dec(j) until c[j].d<=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;

 procedure spread(p,a:longint);
  var i,aux:integer;
   begin
   aux:=0;
    for i:=p to n do
    begin
     if c[i].d = a then
      if c[i].cat>aux then aux:=c[i].cat;
     if c[i].d<> a then break;
    end;
    for i:=p downto 1 do
    begin
     if c[i].d = a then
      if c[i].cat>aux then aux:=c[i].cat;
     if c[i].d<> a then break;
    end;
   max:=aux;
   end;

 procedure caut(a:longint);
  var st,dr,mj:longint;
   begin
    st:=1;
    dr:=n;
    while st<=dr do
     begin
      mj:=(st+dr) div 2;
      if a>c[mj].d then st:=mj+1;
      if a<c[mj].d then dr:=mj-1;
      if a=c[mj].d then break;
     end;
    spread(mj,a);
   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);
 while x>c[1].d-l do
  begin
   maxcat:=0;
   for i:=x-l+1 to x do
    begin
     caut(i);
     if max>maxcat then maxcat:=max;
    end;
   dec(x,l);
   inc(sum,maxcat);
  end;
writeln(fo,sum);
close(fi);
close(fo);
end.