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

Program shuta;

Type
sc=array [1..80,1..80] of longint;

Var
temp1,temp2:longint;
n,i,j,o:integer;
s,h,f:sc;

Begin
assign(input,'shuta.in');
assign(output,'shuta.out');
reset(input);
rewrite(output);
for i:=1 to n do
 for j:=1 to i do
  f[i,j]:=0;
readln(n);
for i:=1 to n do
 for j:=1 to i do
  read(s[i,j]);
h:=s;
for i:=n-1 downto 1 do begin
 for j:=1 to i do begin
  temp1:=h[i,j]+h[i+1,j];
  temp2:=h[i,j]+h[i+1,j+1];
  if temp1>=temp2 then h[i,j]:=temp1
  else begin
   h[i,j]:=temp2;
   f[i,j]:=1;
  end;
 end;
end;
writeln(h[1,1]);
write(s[1,1],' ');
i:=1; j:=1;
repeat
 o:=j+f[i,j];
 i:=i+1;
 write(s[i,o],' ');
 j:=o;
until i=n;
close(input);
close(output);
End.