Pagini recente » Cod sursa (job #3273130) | Cod sursa (job #2396897) | Cod sursa (job #2416862) | Cod sursa (job #2234571) | Cod sursa (job #429559)
Cod sursa(job #429559)
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.