stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll arr[501];

ll dp[501][501];

ll prefix[501];

ll solve(int l, int r){

    if(l == r) return 0;

    if(dp[l][r] != -1) return dp[l][r];

    ll mina = 1e18;

    for(int x=1;x<=r-l;x++){

        ll pre = prefix[l+x-1] -  prefix[l-1];

        ll suf = prefix[r] - prefix[l+x-1];

        mina = min(mina, pre + suf + solve(l, l+x-1) + solve(l+x, r));

    }

    return dp[l][r] = mina;

}

int main(){

    memset(dp, -1, sizeof dp);

    cin>>n;

    for(int x=1;x<=n;x++){

        cin>>arr[x];

        prefix[x] += arr[x] + prefix[x-1];

    }

    cout<<solve(1, n);





}


// Faster C++ solution for the same problem (measured speedup: 1.3022872948279358x):
#include<bits/stdc++.h>

#define int long long

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

#define endl '\n'

//#define for(i,s,n) for(int i=s;i<n;i++) 

#define vii vector<int>

int t = 1, n, OO = 1e14;

vii v, cum;

int dp[402][402];

int solve(int i, int j) {

	if (i + 1 == j) return v[i] + v[j];

	if (i == j) return 0;

	int& ret = dp[i][j];

	if (~ret) return ret;

	ret = OO;

	for (int k = i; k < j; k++) {

		ret = min(ret, (cum[j] - cum[i - 1]) + solve(i, k) + solve(k+1, j));

	}

	return ret;

}

signed main()

{

	fast;

	

	//cin>>t;

	while (t--)

	{

		cin >> n;

		v = vii(n+1);

		for (int i = 1; i <= n; i++) cin >> v[i];

		cum = vii(n + 1);

		for (int i = 1; i <= n; i++) cum[i] = cum[i - 1] + v[i];

		memset(dp, -1, sizeof dp);

		cout<<solve(1,n)<<endl;

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



long long mem[405][405];

int n;

long long arr[405];



long long go(int l,int r)

{

	if(l>=r) return 0;

	if(mem[l][r]!=-1) return mem[l][r];

	long long sum=arr[r]-arr[l-1];

	mem[l][r]=(1LL<<60);

	for(int i=l;i<r;i++)

	{

		mem[l][r]=min(mem[l][r],sum+go(l,i)+go(i+1,r));

	}

	return mem[l][r];

}



int main()

{

	cin >> n;

	for(int i=1;i<=n;i++)

	{

		cin >> arr[i];

		arr[i]+=arr[i-1];

	}

	memset(mem,-1,sizeof mem);

	cout << go(1,n) << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.315495184177029x):
#include <bits/stdc++.h>



using namespace std;



long long mem[405][405];

int ans[405][405];

int n;

long long arr[405];





int main()

{

	cin >> n;

	for(int i=1;i<=n;i++)

	{

		cin >> arr[i];

		arr[i]+=arr[i-1];

	}

	for(int i=1;i<=n;i++)

	{

		mem[i][i]=0;

		ans[i][i]=i;

	}

	for(int len=1;len<n;len++)

	{

		for(int i=1;i+len<=n;i++)

		{

			int j=i+len;

			int ll=ans[i][j-1],rr=ans[i+1][j];

			mem[i][j]=(1LL<<60);

			for(int k=ll;k<=rr;k++)

			{

				long long cur=arr[j]-arr[i-1]+mem[i][k]+mem[k+1][j];

				if(cur<mem[i][j])

				{

					mem[i][j]=cur;

					ans[i][j]=k;

				}

			}

		}

	}

	cout << mem[1][n] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

typedef pair<int, pii> piii;

typedef vector<int> vi;

typedef vector<ll> vll;



#define pb push_back

#define mp make_pair

#define endl '\n'

#define ff first

#define ss second

#define sz(a) ((int)(a).size())

#define rep(i,a,b) for(int i=(a); i<(b); i++)

#define read(v, a, b) for(int i=(a); i<(b); i++) cin>>v[i]

#define clr(a,v) memset(a, v, sizeof(a))

#define all(a) (a).begin(),(a).end()

#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)

#define db(x) cerr << #x << " == " << x << endl

#define _ << " " <<



const int maxn = 450;

const ll inf = 0x3f3f3f3f3f3f3f3f;



int a[maxn];

ll dp[maxn][maxn], sum[maxn];



ll solve(int l, int r){

	if(l >= r) return 0;

	if(dp[l][r] != -1) return dp[l][r];

	

	ll ans = inf;

	

	rep(i,l,r){

		ans = min(ans, solve(l, i) + solve(i+1, r));

	}

	

	return dp[l][r] = ans + sum[r] - sum[l-1];

}



int main(){

	int n; scanf("%d", &n);

	

	rep(i,1,n+1){

		scanf("%d", &a[i]);

		sum[i] = sum[i-1] + a[i];

	}

	

	clr(dp, -1);

	

	printf("%lld\n", solve(1, n));

}


// Faster C++ solution for the same problem (measured speedup: 2.6164378957740317x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using pii = pair<int, int>;

using vi = vector<int>;



#ifdef MY_DEBUG_FLAG

template<typename T> void debug(T a) { cerr << a << ' '; }

template<typename T, typename U> void debug(pair<T, U> a) { cerr << a.first << ' ' << a.second << ' '; }

template<typename T> void debug(vector<T> a) { for(auto it : a) debug(it);}

template<typename T> void debug(set<T> a) { for(auto it : a) debug(it);}

#define db(a) cerr << "DEBUG ( " << #a << " == ", debug(a), cerr << ")\n"

#else

#define db(...)

#endif



#define pb push_back

#define eb emplace_back

#define ff first

#define ss second

#define fast ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr)

#define sz(a) ((int)(a).size())

#define rep(i,a,b) for(int i=(a); i<(b); i++)

#define dec(i,n,a) for(int i=(n); i>=(a); i--)

#define clr(a,v) memset(a, v, sizeof(a))

#define all(a) (a).begin(),(a).end()



constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

constexpr int MAXN = 410;

constexpr int mod = 1000000007;



ll pref[MAXN], dp[MAXN][MAXN];



int main() {

	int n; scanf("%d", &n);

	vi a(n+1); rep(i,1,n+1) scanf("%d", &a[i]);

	rep(i,1,n+1) pref[i] = pref[i-1] + a[i];



	for(int i = n; i >= 1; i--) {

		for(int j = i+1; j <= n; j++) {

			ll add = inf;

			for(int k = i; k < j; k++) {

				add = min(add, dp[i][k] + dp[k+1][j]);

			}

			dp[i][j] = add + pref[j] - pref[i-1];

		}

	}

	printf("%lld\n", dp[1][n]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define int long long

#define INF 1e18



int n;

vector<int> v;

vector<int> pref;



int memo[409][409];



int dp(int l, int r){

    if(l >= r) return 0;

    if(l+1 == r) return v[l]+v[r];

    if(memo[l][r] != -1) return memo[l][r];

    memo[l][r] = INF;

    for(int i  = l; i <= r; i++){

        memo[l][r] = min(memo[l][r], dp(l,i)+dp(i+1,r)+pref[r]-pref[l-1]);

    }

    return memo[l][r];

}



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n;

    v.resize(n+1);

    pref.resize(n+1);

    fill(pref.begin(), pref.end(), 0);

    for(int i = 1; i <= n; i++){

        cin >> v[i];

        pref[i] += pref[i-1];

        pref[i] += v[i];

    }

    for(int i = 0 ; i < 409; i++){

        for(int j = 0; j < 409; j++){

            memo[i][j] = -1;

        }

    }

    cout << dp(1,n) << endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.32663679795861x):
#include <bits/stdc++.h>

using namespace std;



#define int long long

#define INF 1e18



int n;

vector<int> v;

vector<int> pref;



int memo[409][409];



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n;

    v.resize(n+1);

    pref.resize(n+1);

    fill(pref.begin(), pref.end(), 0);

    for(int i = 1; i <= n; i++){

        cin >> v[i];

        pref[i] += pref[i-1];

        pref[i] += v[i];

    }

    for(int l = n; l >= 0; l--){

        for(int r = l+1; r <= n; r++){

            memo[l][r] = INF;

            for(int i = l; i <= r; i++){

                memo[l][r] = min(memo[l][r], pref[r]-pref[l-1]+memo[l][i]+memo[i+1][r]);

            }

        }

    }

    cout << memo[1][n] << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;



#define pii pair<int,int>

#define pll pair<ll, ll>

#define forn(i, a, b) for(int i = a; i <= b; i++)

#define ford(i, a, b) for(int i = a; i >= b; i--)

#define mp make_pair

#define pb push_back

#define F first

#define S second

#define mod 1000000007



ll a[500];

ll ds[405][405];



ll dp(int s, int e){

	if(s >= e) return 0;

	ll &ans = ds[s][e];

	if(ans != -1) return ans;

	ll ls = 0;

	ll rs = 0;

	forn(i, s, e){

		rs += a[i];

	}

	ans = 1e18;

	forn(i, s, e - 1){

		ls += a[i];

		rs -= a[i];

		ans = min(ans, ls + rs + dp(s, i) + dp(i + 1, e));

	}

	return ans;

}



int main(){

	std::ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int n;

	cin >> n;

	forn(i, 0, n - 1){

		cin >> a[i];

	}	

	memset(ds, -1, sizeof(ds));

	cout << dp(0, n - 1) << "\n";

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.299952227955796x):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;



#define pii pair<int,int>

#define pll pair<ll, ll>

#define forn(i, a, b) for(int i = a; i <= b; i++)

#define ford(i, a, b) for(int i = a; i >= b; i--)

#define mp make_pair

#define pb push_back

#define F first

#define S second

#define mod 1000000007



ll a[500];

ll dp[405][405];





int main(){

	std::ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int n;

	cin >> n;

	forn(i, 0, n - 1){

		cin >> a[i];

	}

	forn(diff, 1, n){

		forn(s, 0, n - 1){

			int e = s + diff;

			if(e > n - 1) break;

			ll &ans = dp[s][e];

			ll ls = 0;

			ll rs = 0;

			forn(i, s, e){

				rs += a[i];

			}

			ans = 1e18;

			forn(i, s, e - 1){

				ls += a[i];

				rs -= a[i];

				ans = min(ans, ls + rs + dp[s][i] + dp[i + 1][e]);

			}

		}

	}	

	cout << dp[0][n - 1] << "\n";

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int i = a;i < b;++i) cout << ary[i] << (b-1 == i ? "]\n" : ", "); } while(0)

#define p_map(map,it) do {cout << "{";for (auto it = map.begin();;++it) {if (it == map.end()) {cout << "}\n";break;}else cout << "" << it->first << "=>" << it->second << ", ";}}while(0)



int n;

ll sums[410];

vector<vector<ll>> dp(410,vector<ll>(410,-1));



ll rec(int l,int r) {

    if (dp[l][r] > -1) return dp[l][r];

    ll res = INT64_MAX;

    for (int i = l;i < r;++i) {

        ll temp = rec(l,i)+rec(i+1,r);

        res = min(res,temp);

    }

    return dp[l][r] = res+sums[r+1]-sums[l];

}



int main() {

    cin >> n;

    for (int i = 0;i < n;++i) {

        cin >> sums[i+1];

        sums[i+1] += sums[i];

        dp[i][i] = 0;

    }

    cout << rec(0,n-1) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.3931403570195515x):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)

#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)



ll rec(int l,int r,vector<vector<ll>>& dp,vector<ll>& sums) {

    if (dp[l][r]) return dp[l][r];

    ll ret = INT64_MAX;

    if (r-l) {

        for (int i = l;i < r;++i) ret = min(ret,rec(l,i,dp,sums)+rec(i+1,r,dp,sums)+sums[r+1]-sums[l]);

    } else ret = 0;

    return dp[l][r] = ret;

}



int main() {

    int n;

    cin >> n;

    vector<ll> a(n),sums(n+1,0);

    vector<vector<ll>> dp(n,vector<ll>(n,0));

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

    for (int i = 0;i < n;++i) sums[i+1] = sums[i]+a[i];

    cout << rec(0,n-1,dp,sums) << endl;

    return 0;

    

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int i = a;i < b;++i) cout << ary[i] << (b-1 == i ? "]\n" : ", "); } while(0)

#define p_map(map,it) do {cout << "{";for (auto it = map.begin();;++it) {if (it == map.end()) {cout << "}\n";break;}else cout << "" << it->first << "=>" << it->second << ", ";}}while(0)



int n;

ll sums[410];

vector<vector<ll>> dp(410,vector<ll>(410,0));



int main() {

    cin >> n;

    for (int i = 0;i < n;++i) {

        cin >> sums[i+1];

        sums[i+1] += sums[i];

    }

    for (int i = 1;i < n;++i) for (int j = 0;j < n-i;++j) {

        ll res = INT64_MAX;

        for (int k = j;k < j+i;++k) {

            ll temp = dp[j][k]+dp[k+1][j+i];

            res = min(res,temp);

        }

        dp[j][j+i] = res+sums[j+i+1]-sums[j];

    }

    cout << dp[0][n-1] << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.392797309219971x):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)

#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)



ll rec(int l,int r,vector<vector<ll>>& dp,vector<ll>& sums) {

    if (dp[l][r]) return dp[l][r];

    ll ret = INT64_MAX;

    if (r-l) {

        for (int i = l;i < r;++i) ret = min(ret,rec(l,i,dp,sums)+rec(i+1,r,dp,sums)+sums[r+1]-sums[l]);

    } else ret = 0;

    return dp[l][r] = ret;

}



int main() {

    int n;

    cin >> n;

    vector<ll> a(n),sums(n+1,0);

    vector<vector<ll>> dp(n,vector<ll>(n,0));

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

    for (int i = 0;i < n;++i) sums[i+1] = sums[i]+a[i];

    cout << rec(0,n-1,dp,sums) << endl;

    return 0;

    

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int i = a;i < b;++i) cout << ary[i] << (b-1 == i ? "]\n" : ", "); } while(0)

#define p_map(map,it) do {cout << "{";for (auto it = map.begin();;++it) {if (it == map.end()) {cout << "}\n";break;}else cout << "" << it->first << "=>" << it->second << ", ";}}while(0)



int n;

ll sums[410];

vector<vector<ll>> dp(410,vector<ll>(410,-1));



ll rec(int l,int r) {

    if (dp[l][r] > -1) return dp[l][r];

    ll res = INT64_MAX;

    for (int i = l;i < r;++i) {

        ll temp = rec(l,i)+rec(i+1,r);

        res = min(res,temp);

    }

    return dp[l][r] = res+sums[r+1]-sums[l];

}



int main() {

    cin >> n;

    for (int i = 0;i < n;++i) {

        cin >> sums[i+1];

        sums[i+1] += sums[i];

        dp[i][i] = 0;

    }

    cout << rec(0,n-1) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.4241791239748185x):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int,int> P;

ll const INF = 1LL<<60;



#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)

#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)



int n;

ll dp[410][410];

int a[410];

ll sums[410];



ll rec(int l,int r) {

    if (dp[l][r] > 0) return dp[l][r];

    dp[l][r] = INF;

    for (int i = l;i < r;++i) dp[l][r] = min(dp[l][r],rec(l,i)+rec(i+1,r));

    if (l == r) dp[l][r] = -a[l];

    dp[l][r] += sums[r+1]-sums[l];

    return dp[l][r];

}



int main() {

    cin >> n;

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

    for (int i = 0;i < n+1;++i) for (int j = 0;j < n+1;++j) dp[i][j] = 0;

    sums[0] = 0;

    for (int i = 0;i < n;++i) sums[i+1] = sums[i]+a[i];

    cout << rec(0,n-1) << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;



#define p_ary(ary,a,b,i) do { cout << "["; for (int i = a;i < b;++i) cout << ary[i] << (b-1 == i ? "]\n" : ", "); } while(0)

#define p_map(map,it) do {cout << "{";for (auto it = map.begin();;++it) {if (it == map.end()) {cout << "}\n";break;}else cout << "" << it->first << "=>" << it->second << ", ";}}while(0)



int n;

ll sums[410];

vector<vector<ll>> dp(410,vector<ll>(410,0));



int main() {

    cin >> n;

    for (int i = 0;i < n;++i) {

        cin >> sums[i+1];

        sums[i+1] += sums[i];

    }

    for (int i = 1;i < n;++i) for (int j = 0;j < n-i;++j) {

        ll res = INT64_MAX;

        for (int k = j;k < j+i;++k) {

            ll temp = dp[j][k]+dp[k+1][j+i];

            res = min(res,temp);

        }

        dp[j][j+i] = res+sums[j+i+1]-sums[j];

    }

    cout << dp[0][n-1] << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.4238316268830458x):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int,int> P;

ll const INF = 1LL<<60;



#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)

#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)



int n;

ll dp[410][410];

int a[410];

ll sums[410];



ll rec(int l,int r) {

    if (dp[l][r] > 0) return dp[l][r];

    dp[l][r] = INF;

    for (int i = l;i < r;++i) dp[l][r] = min(dp[l][r],rec(l,i)+rec(i+1,r));

    if (l == r) dp[l][r] = -a[l];

    dp[l][r] += sums[r+1]-sums[l];

    return dp[l][r];

}



int main() {

    cin >> n;

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

    for (int i = 0;i < n+1;++i) for (int j = 0;j < n+1;++j) dp[i][j] = 0;

    sums[0] = 0;

    for (int i = 0;i < n;++i) sums[i+1] = sums[i]+a[i];

    cout << rec(0,n-1) << endl;

    return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <cassert>

#include <cstring>

#include <iostream>

#include <vector>

using namespace std;



const int N_MAX = 405;



int N;

long long A[N_MAX], prefix_sum[N_MAX];

long long dp[N_MAX][N_MAX];



int main() {

    scanf("%d", &N);

    prefix_sum[0] = 0;

    memset(dp, 63, sizeof(dp));



    for (int i = 0; i < N; i++) {

        scanf("%lld", &A[i]);

        prefix_sum[i + 1] = prefix_sum[i] + A[i];

        dp[i][i] = 0;

        dp[i][i + 1] = A[i];

    }



    for (int i = N - 1; i >= 0; i--)

        for (int j = i + 2; j <= N; j++)

            for (int k = i + 1; k < j; k++)

                dp[i][j] = min(dp[i][j], prefix_sum[j] - prefix_sum[i] + dp[i][k] + dp[k][j]);



    printf("%lld\n", dp[0][N] - prefix_sum[N]);

}


// Faster C++ solution for the same problem (measured speedup: 2.2850744172389925x):
#include <algorithm>

#include <cassert>

#include <cstring>

#include <iostream>

#include <vector>

using namespace std;



const long long LL_INF = (long long) 2e18 + 5;



int N;

vector<long long> A, prefix_sum;

vector<vector<long long>> dp;



int main() {

    scanf("%d", &N);

    A.resize(N);

    prefix_sum.assign(N + 1, 0);

    dp.assign(N + 1, vector<long long>(N + 1, LL_INF));



    for (int i = 0; i < N; i++) {

        scanf("%lld", &A[i]);

        prefix_sum[i + 1] = prefix_sum[i] + A[i];

        dp[i][i] = 0;

        dp[i][i + 1] = A[i];

    }



    for (int i = N - 1; i >= 0; i--)

        for (int j = i + 2; j <= N; j++)

            for (int k = i + 1; k < j; k++)

                dp[i][j] = min(dp[i][j], prefix_sum[j] - prefix_sum[i] + dp[i][k] + dp[k][j]);



    printf("%lld\n", dp[0][N] - prefix_sum[N]);

}
// Slower C++ solution:
#include <algorithm>

#include <cassert>

#include <cstring>

#include <iostream>

#include <vector>

using namespace std;



const int N_MAX = 405;



int N;

long long A[N_MAX], prefix_sum[N_MAX];

long long dp[N_MAX][N_MAX];



int main() {

    scanf("%d", &N);

    prefix_sum[0] = 0;

    memset(dp, 63, sizeof(dp));



    for (int i = 0; i < N; i++) {

        scanf("%lld", &A[i]);

        prefix_sum[i + 1] = prefix_sum[i] + A[i];

        dp[i][i] = 0;

        dp[i][i + 1] = A[i];

    }



    for (int i = N - 1; i >= 0; i--)

        for (int j = i + 2; j <= N; j++)

            for (int k = i + 1; k < j; k++)

                dp[i][j] = min(dp[i][j], prefix_sum[j] - prefix_sum[i] + dp[i][k] + dp[k][j]);



    printf("%lld\n", dp[0][N] - prefix_sum[N]);

}


// Faster C++ solution for the same problem (measured speedup: 2.2997789203798447x):
#include <algorithm>

#include <cassert>

#include <iostream>

#include <vector>

using namespace std;



const long long LL_INF = (long long) 2e18 + 5;



int N;

vector<long long> A, prefix_sum;

vector<vector<long long>> dp;

vector<vector<int16_t>> opt;



int main() {

    scanf("%d", &N);

    A.resize(N);

    prefix_sum.assign(N + 1, 0);



    for (int i = 0; i < N; i++) {

        scanf("%lld", &A[i]);

        prefix_sum[i + 1] = prefix_sum[i] + A[i];

    }



    dp.assign(N + 1, vector<long long>(N + 1, LL_INF));

    opt.assign(N + 1, vector<int16_t>(N + 1, -1));



    for (int i = 0; i < N; i++) {

        dp[i][i + 1] = 0;

        opt[i][i + 1] = i;

    }



    // Knuth optimization: opt[i][j - 1] <= opt[i][j] <= opt[i + 1][j].

    for (int i = N - 1; i >= 0; i--)

        for (int j = i + 2; j <= N; j++)

            for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {

                long long candidate = dp[i][k] + dp[k][j] + prefix_sum[j] - prefix_sum[i];



                if (candidate < dp[i][j]) {

                    dp[i][j] = candidate;

                    opt[i][j] = k;

                }

            }



    printf("%lld\n", dp[0][N]);

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



using ll = long long;



int n;

vector<ll> arr, ps;

vector<vector<ll>> dp;



ll solve(int x, int y){

    if(x == y) return 0;

    if(dp[x][y] != -1) return dp[x][y];

    // if(x > y) return 0;

    ll mn = LONG_LONG_MAX;

    for(int p = x + 1; p <= y; p++){

        ll l = solve(x, p-1);

        ll r = solve(p, y);

        if(x == 0){

            l += ps[y];

        }else{

            l += ps[y] - ps[x-1];

        }

        mn = min(mn, l + r);

    }

    return dp[x][y] = mn;

}



int main(){

    cin>>n;

    arr.resize(n);

    ps.resize(n, 0);

    dp.resize(405, vector<ll>(405, -1));

    ll cur = 0;

    for(int i = 0; i < n; i++){

        cin>>arr[i];

        cur += arr[i];

        ps[i] = cur;

    }

    ll res = solve(0, n-1);

    cout<<res<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.605987365681869x):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;



int n;

vector<ll> a, csum;

vector<vector<ll>> dp;



ll sum(int l, int r){

    if(l == 0) return csum[r];

    return csum[r] - csum[l-1];

}



// ll solve(int l, int r){

//     if(l >= r) return 0;

//     ll res = LLONG_MAX;

//     for(int k = l; k < r; k++){

//         res = min(res, solve(l, k) + solve(k+1, r) + sum(l, r));

//     }

//     return res;

// }



int main(){

    cin>>n;

    a.resize(n); csum.resize(n);

    for(int i = 0; i < n; i++){

        cin>>a[i];

    }

    csum[0] = a[0];

    for(int i = 1; i < n; i++){

        csum[i] = csum[i-1] + a[i];

    }

    // ll res = solve(0, n-1);

    dp.resize(n, vector<ll>(n));

    for(int l = n - 1; l >= 0; l--){

        for(int r = l + 1; r < n; r++){

            dp[l][r] = LLONG_MAX;

            for(int k = l; k < r; k++){

                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + sum(l, r));

            }



        }

    }

    ll res = dp[0][n-1];

    cout<<res<<endl;

    return 0;

}