CUBE-T025: A-Point

#include <iostream>
#include <vector>
using namespace std;
typedef long long lli;

vector<int> qsum;
int n;

vector<vector<lli>> memo;
lli Separate(int s, int e){
    if(memo[s][e] != -1){
        return memo[s][e];
    }
    if(s == e){
        return memo[s][e] = 0;
    } else {
        int x1, x2;
        lli mx = 0;
        for(int i = s; i < e; ++i){
            x1 = qsum[i] - qsum[s - 1];
            x2 = qsum[e] - qsum[i];
            mx = max(mx, 2 * min(x1, x2) + max(x1, x2) + Separate(s, i) + Separate(i + 1, e));
        }
        return memo[s][e] = mx;
    }
}

void PrintQSum(){
    for(int i = 1; i <= n; ++i){
        cout << qsum[i] << " ";
    }
    cout << "\n";
    return;
}

int main(){

    int x;

    scanf("%d", &n);
    qsum.assign(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &x);
        qsum[i] = qsum[i - 1] + x;
    }

    memo.assign(n + 1, vector<lli>(n + 1, -1));
    cout << Separate(1, n);

    return 0;
}