Cod sursa(job #72943)

Utilizator FoaiaFoaia de Hartie Foaia Data 15 iulie 2007 22:20:29
Problema Lupul Urias si Rau Scor 64
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.7 kb
var a,b,vi,vs:array[0..100000] of longint;
    f1,f2:text;
    ii,i,j,x,n,l,max,nr,s,k,p,ind,h:longint;

procedure pozitie(var m:longint; p,u:longint);
var i,j,di,dj,aux:longint;
begin
     di:=0;
     dj:=-1;
     i:=p;
     j:=u;
     while i<j do
     begin
          if a[i]>a[j] then
          begin
               aux:=di;
               di:=-dj;
               dj:=-aux;
               aux:=a[i];
               a[i]:=a[j];
               a[j]:=aux;
               aux:=b[i];
               b[i]:=b[j];
               b[j]:=aux;
          end;
          if a[i]=a[j] then
                if b[i]<b[j] then
                begin
                        aux:=di;
                        di:=-dj;
                        dj:=-aux;
                        aux:=a[i];
                        a[i]:=a[j];
                        a[j]:=aux;
                        aux:=b[i];
                        b[i]:=b[j];
                        b[j]:=aux;
                end;
          i:=i+di;
          j:=j+dj;
     end;
     m:=i;
end;

procedure quick(p,u:longint);
var m:longint;
begin
     if p<u then
     begin
          pozitie(m,p,u);
          quick(p,m-1);
          quick(m+1,u);
     end;
end;

begin
        assign(f1,'lupu.in');
        reset(f1);
        assign(f2,'lupu.out');
        rewrite(f2);
        read(f1,n,x,l);
        s:=x div l;
        if x mod l>0 then inc(s);
        for i:=1 to n do
        begin
             readln(f1,p,k);
             if p<>0 then
             begin
                  inc(j);
                  a[j]:=(p+l-1) div l;
                  b[j]:=k;
             end
             else
             begin
                   if x mod l=0 then
                   begin
                        inc(j);
                        h:=1;
                        a[j]:=-1;
                        b[j]:=k;
                   end;
             end;
        end;
        quick(1,j);
        if h=1 then inc(s);
        for i:=1 to n do
                if a[i]<>a[i-1] then
                begin
                        inc(ii);
                        vi[ii]:=i;
                        vs[ii-1]:=i-1;
                end;
        vs[ii]:=i;
        for i:=1 to s do
        begin
                max:=-maxlongint;
                for j:=1 to i do
                begin
                      if (b[vi[j]]>max)and(vi[j]<=vs[j]) then
                      begin
                           max:=b[vi[j]];
                           ind:=j;
                      end;
                end;
                nr:=nr+max;
                inc(vi[ind]);
        end;
        writeln(f2,nr);
        close(f1);
        close(f2);
end.