ELEVATOR - Thang máy vũ trụ
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+,S+}
PROGRAM ELEVATOR;
CONST
fi='';
fo='';
max=40000;
maxn=400;
TYPE
rec=record a:longint; h,c:byte; end;
VAR
n:integer;
k:array[1..maxn] of rec;
d:array[0..max] of integer;
trace:array[0..max] of integer;
kq:longint;
Procedure ReadInput;
Var
f:text;
i:integer;
Begin
Assign(f,fi); Reset(f);
Readln(f,n);
For i:=1 to n do
with k[i] do
Readln(f,h,a,c);
Close(f);
End;
Procedure QuickSort;
Procedure Sort(l,r:integer);
Var
i,j:integer;
x:longint;
tg:rec;
Begin
i:=l; j:=r; x:=k[(l+r) div 2].a;
repeat
while k[i].a<x do inc(i);
while k[j].a>x do dec(j);
if i<=j then
begin
tg:=k[i]; k[i]:=k[j]; k[j]:=tg;
inc(i); dec(j);
end;
until i>j;
if i<r then Sort(i,r);
if l<j then Sort(l,j);
End;
Begin
Sort(1,n);
End;
Procedure Solve;
Var
i,j,l,m:longint;
Begin
kq:=0; d[0]:=1;
For i:=1 to n do
For j:=k[i].c downto 1 do
For l:=k[i].a-j*k[i].h downto 0 do
if (d[l]=1) and (d[l+j*k[i].h]=0) and (trace[l]<>i) then
begin
m:=l+j*k[i].h;
d[m]:=1; trace[m]:=i;
if m>kq then kq:=m;
end;
End;
Procedure WriteOutput;
Var
f:text;
Begin
Assign(f,fo); Rewrite(f);
Writeln(f,kq);
Close(f);
End;
BEGIN
ReadInput;
QuickSort;
Solve;
WriteOutput;
END.