#include <stdio.h> #include <stdlib.h> #define MAX_N 80 int max(int a, int b) { return a > b ? a : b; } int main() { int n; int tower[MAX_N][MAX_N]; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { scanf("%d", &tower[i][j]); } } int dp[MAX_N][MAX_N]; for (int i = 0; i < n; i++) { dp[n-1][i] = tower[n-1][i]; } for (int i = n-2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tower[i][j]; } } int path[MAX_N]; int cur = 0; path[cur++] = tower[0][0]; int x = 0, y = 0; while (cur < n) { if (dp[x+1][y] > dp[x+1][y+1]) { path[cur++] = tower[x+1][y]; x++; } else { path[cur++] = tower[x+1][y+1]; x++; y++; } } printf("%d\n", dp[0][0]); for (int i = 0; i < n; i++) { printf("%d ", path[i]); } printf("\n"); return 0; }