记录编号	1222	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-07-25 10:39:26	内存使用	0.00 MiB

program shuta;
const
maxline=80;

var
line:integer;
a,max,flag:array[1..maxline,1..maxline] of longint;
b:array[1..maxline] of longint;

function maxsum(i,j:integer):integer;
begin
if i=line then
 maxsum:=a[i,j]
 else if maxsum(i+1,j)>maxsum(i+1,j+1)
      then maxsum:=maxsum(i+1,j)+a[i,j]
      else maxsum:=maxsum(i+1,j+1)+a[i,j];
 b[i]:=a[i,j];
 end;

procedure ini;
var
i,j:integer;
begin
assign(input,'shuta.in');
reset(input);
assign(output,'shuta.out');
rewrite(output);
readln(line);
for i:=1 to line do
 begin
 for j:=1 to i do
 read(a[i,j]);
 max[i,j]:=a[i,j];
 readln;
 end;
close(input);
fillchar(flag,sizeof(flag),0);
end;

procedure main;
var
i,j,d,k:integer;
begin
b[1]:=a[1,1];
for i:=line downto 1 do
 begin
 if i=line then for j:=1 to i do max[i,j]:=a[i,j]
 else
  begin
  for j:=1 to i do
  if a[i,j]+max[i+1,j]>a[i,j]+max[i+1,j+1] then begin max[i,j]:=a[i,j]+max[i+1,j]; flag[i,j]:=0 end
                                           else begin max[i,j]:=a[i,j]+max[i+1,j+1]; flag[i,j]:=1 end;
  end;
 end;
end;

procedure print;
var
i,j:integer;
begin
writeln(max[1,1]);
j:=1;
for i:=1 to line-1 do
 begin
 write(a[i,j],' ');
 j:=j+flag[i,j];
 end;
writeln(a[line,j]);
close(output);
end;

begin
ini;
main;
print;
end.