Cod sursa(job #429559)

Utilizator al3csutzuSirbu Alexandru al3csutzu Data 30 martie 2010 11:41:41
Problema Gutui Scor 80
Compilator fpc Status done
Runda teme_upb Marime 1.51 kb
program gutuia;
type vector=array[0..100000] of longint;
var f,g:text;
n,i,j,u,h,nr,best:longint;
inalt,greut,aux1,aux2,max,maxcur:vector;

procedure qsort(i:longint;j:longint; var  inalt:vector;var  greut:vector;var aux1:vector;var aux2:vector);
var poz,k,st,fn:longint;
begin
  if (i<j) then
  begin
    st:=i-1; fn:=j+1;
    for k:=i+1 to j do
    if inalt[i]>inalt[k] then
    begin
      fn:=fn-1; aux1[fn]:=inalt[k]; aux2[fn]:=greut[k];
    end
    else
    begin
      st:=st+1; aux1[st]:=inalt[k]; aux2[st]:=greut[k];
    end;
    poz:=st+1;
    inalt[poz]:=inalt[i]; greut[poz]:=greut[i];
    for k:=i to j do
      if k<>poz then
      begin
        inalt[k]:=aux1[k];
        greut[k]:=aux2[k];
      end;

    qsort(i,poz-1,inalt,greut,aux1,aux2);
    qsort(poz+1,j,inalt,greut,aux1,aux2);
  end;
end;


begin
  assign(f,'gutui.in'); assign(g,'gutui.out');
  reset(f); rewrite(g);
  read(f,n,h,u);
  for i:=1 to n do
    read(f,inalt[i],greut[i]);
  qsort(1,n,inalt,greut,aux1,aux2);
  if greut[1]<h then begin max[1]:=greut[1]; nr:=1; end;
  for i:=2 to n do
  begin
    for j:=0 to nr do
      if (inalt[i]+j*u<=h) then
      begin
        if max[j]+greut[i]>max[j+1] then maxcur[j+1]:=max[j]+greut[i]
        else maxcur[j+1]:=max[j+1];
      end
      else break;
    if maxcur[nr+1]<>0 then nr:=nr+1;
    for j:=1 to nr do max[j]:=maxcur[j];
  end;
  best:=max[1];
  for i:=2 to nr do
    if best<max[i] then best:=max[i];
  writeln(g,best);
  close(f); close(g);
end.