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.

Download