记录编号	548569	评测结果	AAAAAAAAAA
题目名称	[IOI 1994] 数塔	最终得分	100
用户昵称	发光二向箔	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2020-01-26 15:59:11	内存使用	13.73 MiB

#include <iostream>
#include <cstdio>
using namespace std;
struct code {
	int zhi,path;
};
code f[81][81],mx;
int a[81][81]={0},n;
void print (int x,int y,int z) {
	if (x==1) return ;
	if (a[x-1][z]==y) {
		print(x-1,f[x-1][z].path,z);
	}
	else print(x-1,f[x-1][z-1].path,z-1);
	printf("%d ",y);
}
int main()
{
	//ios::sync_with_stdio(false);      //greater<int>()
	freopen("shuta.in","r",stdin);
	freopen("shuta.out","w",stdout);
	scanf("%d",&n);
	for (int q=1;q<=n;q++) {
		for (int w=1;w<=q;w++) {
			scanf("%d",&a[q][w]);
			if (f[q-1][w].zhi>f[q-1][w-1].zhi) {
				f[q][w].zhi=f[q-1][w].zhi+a[q][w];
				f[q][w].path=a[q-1][w];
			}
			else {
				f[q][w].zhi=f[q-1][w-1].zhi+a[q][w];
				f[q][w].path=a[q-1][w-1];
			}
		}
	}
	mx.zhi=-1;
	for (int q=1;q<=n;q++) 
		if (f[n][q].zhi>mx.zhi) {
			mx.zhi=f[n][q].zhi;
			mx.path=q;
		}
	printf("%d\n",mx.zhi);
	print(n,f[n][mx.path].path,mx.path);
	printf("%d\n",a[n][mx.path]);
	return 0;
}