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.

Download