stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



// Header files, namespaces,

// macros as defined above

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>





#define f first

#define s second

#define db long double

#define pb push_back

#define sz(c) (c).size()

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



typedef long long ll;

typedef pair <int , int> ii;

typedef pair <ii , int> iii;

typedef vector <int> vi;

typedef vector <ii> vii;

typedef vector <iii> viii;

typedef vector <vi> vvi;

typedef vector <vii> vvii;



const ll mod = 1e9+7;

const int MAX = 4e2+5;

const db eps = 1e-13;



ll memo[MAX][MAX] , v[MAX];





ll dp ( int lo , int hi ) {



    if( hi==lo )

        return 0;



    ll &res = memo[lo][hi];



    if( res != -1 )

        return res;



    res = 1e18;



    for( int i = lo ; i < hi ; i++ ) {



        res = min( ( dp( lo , i ) + dp( i+1 , hi ) ) + (v[i] - v[lo-1]) + (v[hi] - v[i]) , res );



    }



    return res;

}



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

    cout<<setprecision(11)<<fixed;

    memset( memo , -1 , sizeof memo );

    int n;cin>>n;

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

        cin>>v[i];

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



    }



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



}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



    for(int sz = 2; sz < n; sz++){

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



long long int dp[404][404];

int n;

long long int a[404];



long long int fn(int i, int j) {

    if (i == j) return 0;

    if (~dp[i][j]) return dp[i][j];

    dp[i][j] = LLONG_MAX;

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

        dp[i][j] = min(dp[i][j], fn(i, k) + fn(k + 1, j) + (a[j] - (i > 0? a[i - 1] : 0))); 

    }

    return dp[i][j];

}



int main() {

    scanf("%d", &n);

    scanf("%lld", &a[0]);

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

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

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

    }

    memset(dp, -1, sizeof dp);

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

    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



    for(int sz = 2; sz < n; sz++){

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef double dd;

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

#define endl "\n"

#define clr (n, r) memset(n,r,sizeof(n));



void fast() {

    cin.tie(0);

    cin.sync_with_stdio(0);

}



const ll MAX = 405;

ll n, arr[MAX], dp[MAX][MAX], pre[MAX];



ll ans(ll i = 0, ll j = n-1) {

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

    if(~ret)return ret;

    if(i<0||j<0||i==n||j==n)return 0;

    if (i == j)return arr[i];

    if (i > j)return 0;

    ll solu = 1e15;

    ll res = 0;

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

        res = ans(i, k) + ans(k + 1, j) + pre[j + 1] - pre[i];

       // cout<<i<<" "<<j<<endl;

        solu = min(solu, res);

    }

    return ret=solu;

}



int main() {

    fast();

    cin >> n;

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

        cin >> arr[i];

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

    }

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

    cout << ans()-pre[n];

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



    for(int sz = 2; sz < n; sz++){

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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));

}


// Optimized solution to the same problem (faster):
#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]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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]);

}


// Optimized solution to the same problem (faster):
#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]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem: