ELEVATOR - Thang máy vũ trụ
Tác giả: flashmt
Ngôn ngữ: Pascal
const maxk=40000;
maxn=400;
var a:array[1..maxn] of longint;
h,c:array[1..maxn] of integer;
f:array[0..1,0..maxk] of longint;
n:integer;
re:longint;
procedure rf;
var i:integer;
begin
readln(n);
for i:=1 to n do readln(h[i],a[i],c[i]);
end;
procedure sort(l,r:integer);
var i,j:integer; x,y:longint;
begin
i:=l; j:=r; x:=a[(i+j) div 2];
repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=h[i]; h[i]:=h[j]; h[j]:=y;
y:=c[i]; c[i]:=c[j]; c[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure pr;
var i,j,t,k,p:longint;
begin
sort(1,n);
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
begin
t:=i mod 2;
f[t]:=f[1-t];
for j:=1 to c[i] do
begin
p:=h[i]*j;
for k:=p to a[i] do
if f[1-t,k-p]=1 then
f[t,k]:=1;
end;
end;
for i:=a[n] downto 0 do
if f[t,i]=1 then break;
re:=i;
end;
procedure wf;
begin
write(re);
end;
begin
rf;
pr;
wf;
end.