sumtri1

#include <bits/stdc++.h>

using namespace std;

ifstream fin("sumtri1.in");
ofstream fout("sumtri1.out");

const int NMAX = 105;

int n;
vector < vector < int > > G(NMAX, vector < int >(NMAX));
vector < vector < int > > G2(NMAX, vector < int >(NMAX));
vector < int > sol(NMAX);

void Read()
{
    fin >> n;
    int i, j, x;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= i; ++j)
        {
            fin >> G[i][j];
            G2[i][j] = G[i][j];
        }
}

void DP()
{
    int i, j;
    for(i = 2; i <= n; ++i)
        for(j = 1; j <= i; ++j)
        {
            if(j == 1)
                G2[i][j] += G2[i-1][j];
            else if(j == i)
                     G2[i][j] += G2[i-1][j-1];
                 else
                     G2[i][j] += min(G2[i-1][j-1], G2[i-1][j]);
        }

}

int main()
{
    Read();
    DP();
    int minn = INT_MAX, i = 1, min_index;
    for(; i <= n; ++i)
        if(G2[n][i] < minn)
        {
            minn = G2[n][i];
            min_index = i;
        }
    fout << minn << endl;
    i = 1;
    int j = min_index;
    sol[i] = G[n][j];
    for(i = 2; i <= n; ++i)
    {
        if(G2[n-i+1][j] > G2[n-i+1][j-1])
            --j;
        if(n-i+1 == j-1)
            --j;
        sol[i] = G[n-i+1][j];
    }

    i = n;
    for(; i >= 1; --i)
        fout << sol[i] <<" ";

    return 0;
}