Submission #2854423

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

const long long INF = LLONG_MAX / 2;

vector<int> a;
vector<vector<long long> > memo;

long long solve(int i, int j)
{
    if(i == j)
        return a[i];
    if(memo[i][j] != -1)
        return memo[i][j];

    long long ans = -INF;
    for(int k=i+1; k<j; ++k){
        long long tmp = solve(i, k-1) + solve(k+1, j);
        ans = max(ans, tmp);
    }
    return memo[i][j] = ans;
}

void output(int i, int j, int offset, vector<int>& ans)
{
    if(i == j)
        return;

    for(int k=i+1; ; ++k){
        long long x = solve(i, k-1) + solve(k+1, j);
        if(x == solve(i, j)){
            output(i, k-1, offset, ans);
            output(k+1, j, offset + 2, ans);
            ans.push_back(offset + 1);
            return;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    a.resize(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];

    memo.assign(n, vector<long long>(n, -1));
    long long ans = -INF;
    pair<int, int> p;
    for(int i=0; i<n; ++i){
        for(int j=i; j<n; ++j){
            long long tmp = solve(i, j);
            if(ans < tmp){
                ans = tmp;
                p = make_pair(i, j);
            }
        }
    }
    cout << ans << endl;

    vector<int> v;
    for(int i=n-1; i>p.second; --i)
        v.push_back(i);
    for(int i=0; i<p.first; ++i)
        v.push_back(0);
    output(p.first, p.second, 0, v);

    cout << v.size() << endl;
    for(int x : v)
        cout << (x + 1) << endl;

    return 0;
}

Submission Info

Judge Result