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

program EmberAsh;
var
a,f:array[0..1000,0..1000]of longint;
max,i,j,k,m,n,t1:longint;
b:array[0..1000]of longint;

BEGIN
assign(input,'shuta.in');reset(input);
assign(output,'shuta.out');rewrite(output);
readln(n);
for i:=1 to n do
  for j:=1 to i do
    read(a[i,j]);
f[1,1]:=a[1,1];
for i:=2 to n do
  for j:=1 to n do
    if a[i,j]+f[i-1,j]>a[i,j]+f[i-1,j-1] then
      f[i,j]:=a[i,j]+f[i-1,j]
      else
      f[i,j]:=a[i,j]+f[i-1,j-1];
for i:=1 to n do
  if f[n,i]>max then
    max:=f[n,i];
for i:=1 to n do
  if f[n,i]=max then
    begin
    m:=n;
    b[m]:=a[n,i];
    dec(m);
    t1:=f[n,i]-a[n,i];
    end;
for i:=n-1 downto 1 do
  for j:=1 to n-1 do
    begin
    if m>=1 then
    if f[i,j]=t1 then
      begin
      b[m]:=a[i,j];
      dec(m);
      t1:=f[i,j]-a[i,j];
      end;
    end;
writeln(max);
for i:=1 to n-1 do
  write(b[i],' ');
writeln(b[n]);
close(input);close(output);
END.