stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<string>

#include<vector>

#include<random>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<algorithm>

#define endl "\n"

#define fi first

#define se second

#define db double

#define gcd __gcd

#define pb push_back

#define mp make_pair

#define lowbit(x) (x & (-x))

#define PII  pair<int, int> 

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

#define debug(x) cout << #x << " = " << x << endl

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

#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)

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

template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }

template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }

typedef long long ll;

typedef unsigned long long ull;

const db eps = 1e-9;

const db PI = acos(-1);

const int inf = 0x3f3f3f3f;

const int mod = (int)1e9 + 7;

const int maxn = (int)4e2 + 5;//remember to modify it, No RE or MLE

const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;



int a[maxn];

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

int n;



int main()

{

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i), sum[i] = sum[i-1] + a[i];

	memset(dp, 0x3f, sizeof dp);

	rep(i, 1, n) dp[i][i] = 0;

	rep(len, 2, n){

		rep(l, 1, n - len + 1){

			int r = l + len - 1;

			rep(mid, l, r - 1){

				dp[l][r] = qmin(dp[l][r], dp[l][mid] + dp[mid+1][r] + sum[r] - sum[l-1]);

			}

		}

	}

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

	return 0;

}

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

using namespace std;

using ll = long long;



int main(){



    cin.tie( nullptr );

    ios_base::sync_with_stdio(0);



    int n; cin >> n;



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

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

        cin >> v[i], v[i]+=v[i-1];



    vector< vector<ll> > dp;

    dp.assign(n+1, vector<ll>(n+1,1e16));



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

    for(int i=1, j=2; j<=n; i++, j++) dp[i][j] = v[j] - v[i-1];



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

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

        ll tot = v[j] - v[i-1];

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

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

    }

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



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

//    for(int j=1; j<=n; j++)

//        cout << dp[i][j] << " \n"[j==n];



    return 0;

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

using namespace std;



int n;

long long arr[401];

long long dp[401][401];



long long getrange(int i, int  j){

	return (arr[j] - (i>0 ? arr[i-1]:0));

}



long long solve(int i, int j){

	if(i==j) return 0;

	if(dp[i][j] != -1) return dp[i][j];



	dp[i][j] = 1e17;

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

		dp[i][j] = min(dp[i][j],

					solve(i, k) + solve(k+1, j)+

					getrange(i, k) + getrange(k+1, j));	

	}

	return dp[i][j];

}



int main(){

	scanf("%d", &n);

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

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

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

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

	}

	memset(dp, -1, sizeof dp);

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

	return 0;

}

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

using namespace std;

using ll = long long;



int main(){



    cin.tie( nullptr );

    ios_base::sync_with_stdio(0);



    int n; cin >> n;



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

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

        cin >> v[i], v[i]+=v[i-1];



    vector< vector<ll> > dp;

    dp.assign(n+1, vector<ll>(n+1,1e16));



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

    for(int i=1, j=2; j<=n; i++, j++) dp[i][j] = v[j] - v[i-1];



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

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

        ll tot = v[j] - v[i-1];

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

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

    }

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



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

//    for(int j=1; j<=n; j++)

//        cout << dp[i][j] << " \n"[j==n];



    return 0;

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

using namespace std;

#define FASTIO  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define ll long long

#define vi vector<ll>

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

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

#define tr(it, a)   for(auto it=a.begin();it!=a.end();it++)

#define pb push_back

#define endl  "\n"

const ll MAX=1e5+5;

const ll mod=1e9+7;

vi v(MAX);

vi pref(MAX);

ll dp[405][405];

ll  fun(ll i,ll k)

{

    if(k==i)

        return 0;

        if(dp[i][k]!=-1)

            return dp[i][k];

    ll ans=1e18;

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

    {

        ans=min(ans,fun(i,j)+fun(j+1,k)+pref[k]-pref[i-1]);

        // cout<<j<<"--> "<<ans<<endl;

    }



    return dp[i][k]=ans;

}

int main()

{

    ll t=1;

   // cin>>t;

    while(t--)

    {



   ll n,k;

   cin>>n;

   pref[0]=0;

   rep(i,1,n+1)

   {

       cin>>v[i];

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



   }

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

   cout<<fun(1,n);

    }

    return 0;

}


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

using namespace std;

#define FASTIO  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define ll long long

#define vi vector<ll>

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

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

#define tr(it, a)   for(auto it=a.begin();it!=a.end();it++)

#define pb push_back

#define endl  "\n"

const ll MAX=1e5+5;

const ll mod=1e9+7;

vi v(MAX);

vi pref(MAX);

ll dp[405][405];

/*

ll  fun(ll i,ll k)

{

    if(k==i)

        return 0;

        if(dp[i][k]!=-1)

            return dp[i][k];

    ll ans=1e18;

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

    {

        ans=min(ans,fun(i,j)+fun(j+1,k)+pref[k]-pref[i-1]);

    }

    return dp[i][k]=ans;

}*/

ll fun(ll n)

{

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

        dp[i][i]=0;

    for(ll len=2;len<=n;len++)

    {

        for(ll i=1;i<=n-len+1;i++)

        {

            ll val=1e18;

            for(ll k=i;k<=i+len-2;k++)

            {

                val=min(val,dp[i][k]+dp[k+1][i+len-1]+pref[i+len-1]-pref[i-1]);

            }

            dp[i][i+len-1]=val;

        }

    }

    /*

    rep(i,1,n+1)

    {

        rep(j,1,n+1)

        {

            cout<<dp[i][j]<<"  ";

        }

        cout<<endl;

    }*/

    return dp[1][n];

}

int main()

{

    ll t=1;

   // cin>>t;

    while(t--)

    {



   ll n,k;

   cin>>n;

   pref[0]=0;

   rep(i,1,n+1)

   {

       cin>>v[i];

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



   }

   cout<<fun(n);

    }

    return 0;

}
// Slower C++ solution:
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;



using ll = long long;

using P = pair<int, int>;



template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}

template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}



constexpr int MOD = 1e9 + 7;

constexpr ll INF = 1e18;

constexpr double pi = acos(-1);

constexpr double EPS = 1e-10;



int dx[] = {1, 0, -1, 0};

int dy[] = {0, -1, 0, 1};



vector<ll> sum(410);

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



// [l, r)

ll solve(int l, int r){

    if(0 <= dp[l][r]) return dp[l][r];

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



    ll val = INF;

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

        // [l, r) -> [l, i) and [i, r)

        ll cost = sum[r] - sum[l];

        chmin(val, solve(l, i) + solve(i, r) + cost);

    }



    return dp[l][r] = val;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n; cin>>n;

    vector<int> a(n);

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

        cin>>a[i];

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

    }



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

}

// Faster C++ solution for the same problem (measured speedup: 1.5382845765406836x):
#pragma GCC optimize("O3")

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <string>

#include <cstring>

#include <deque>

#include <list>

#include <queue>

#include <stack>

#include <vector>

#include <utility>

#include <algorithm>

#include <map>

#include <set>

#include <complex>

#include <cmath>

#include <limits>

#include <cfloat>

#include <climits>

#include <ctime>

#include <cassert>

#include <numeric>

#include <fstream>

#include <functional>

#include <bitset>

using namespace std;



using ll = long long;

using P = pair<int, int>;

using T = tuple<int, int, int>;



template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}

template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}



constexpr int MOD = 1e9 + 7;

constexpr int inf = 1e9;

constexpr long long INF = 1e18;



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



int dx[] = {1, 0, -1, 0};

int dy[] = {0, 1, 0, -1};



vector<ll> sum(410);

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



ll solve(int l, int r){

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

    if(r - l == 1) return 0;



    ll ans = INF;

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

        ll cost = sum[r] - sum[l];

        chmin(ans, solve(l, i) + solve(i, r) + cost);

    }



    return dp[l][r] = ans;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n; cin>>n;

    vector<int> a(n);

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



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



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



    return 0;

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

#define ll long long

using namespace std;

const ll mod=1e9+7;

ll ps[100009],n,a[10009],dp[409][409];



ll f(ll l, ll r){

    if(l==r)return 0;

    ll tmp=1e17;

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

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

        tmp=min(tmp,f(l,i)+f(i+1,r)+ps[r]-ps[l-1]);

    }

    return dp[l][r]=tmp;

}



int main(){

    cin >> n;

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

        cin >> a[i];

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

    }

    memset(dp,-1,sizeof dp);

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

}

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



#define Solved int main()

#define pb push_back

#define mp make_pair

#define F first

#define S second

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

#define forn(i, x) for(int i = 1; i <= x; i++)

#define rep(i, x, y) for(int i = x; i <= y; i++)

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

#define pii pair<int, int>

#define ll long long

#define ull unsigned long long

#define ld long double

#define mii map<int, int>

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

#define lb lower_bound

#define ub upper_bound

using namespace std;



inline ll bip(ll x,ll n,ll mod){ll res=1;while(n){if(n&1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}



const int maxn = 1e9;

const ll inf = 1e18;

//const int mod = 998244353;

const int mod = 1e9 + 7;

const int N = 1e5 + 10;



int n, a[401];

ll sum[401], dp[401][401];



ll rec(int l, int r) {

    if (l == r) return 0;

    if (dp[l][r]) 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));

    }

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

}



void solve() {

    cin >> n;



    forn (i, n)

        cin >> a[i];



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

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



    cout << rec(1, n);

}



Solved {

    SpeedForce;

	int tt = 1;

    //cin >> tt;

	while (tt--) {

		solve();

		cout << '\n';

	}



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

#define ll long long

using namespace std;

const ll mod=1e9+7;

ll ps[100009],n,a[10009],dp[409][409];



ll f(ll l, ll r){

    if(l==r)return 0;

    ll tmp=1e17;

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

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

        tmp=min(tmp,f(l,i)+f(i+1,r)+ps[r]-ps[l-1]);

    }

    return dp[l][r]=tmp;

}



int main(){

    cin >> n;

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

        cin >> a[i];

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

    }

    memset(dp,-1,sizeof dp);

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

}

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

using namespace std;

#define ll long long

ll dp[401][401];

bool v[401][401];

ll minMerge(ll i,ll j,ll* arr)

{

    if(i==j)

        return 0;

    if(v[i][j])

        return dp[i][j];

    v[i][j]=1;

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

    x=LONG_MAX;

    ll tot=0;

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

        tot+=arr[k];

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

    {

        x=min(x,tot+minMerge(i,k-1,arr)+minMerge(k,j,arr));

    }

    return x;

}

int main()

{

    ll n;

    cin>>n;

    ll arr[n+10];

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

    cout<<minMerge(0,n-1,arr);

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

using namespace std;



int const N=4e2+5, M=1e5+5, /*OO = 0x3f3f3f3f,*/ MOD=1e9+7;

long long const OO = 0x3f3f3f3f3f3f3f3f;

int n;

long long arr[N];



long long mem[N][N];

long long solve(int s, int e)

{

    if(s==e)

        return 0;

    if(mem[s][e]!=-1)

        return mem[s][e];

    long long ret=OO;

    for(int i=s; i<e; i++)

        ret=min(ret,solve(s,i)+solve(i+1,e)+arr[e]-arr[s-1]);

    return mem[s][e]=ret;

}





int main()

{

//    freopen("input.txt","rt",stdin);

//    freopen("output.txt","wt",stdout);

    scanf("%d",&n);



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

    {

        scanf("%lld",arr+i);

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

    }

    memset(mem, -1, sizeof mem);

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





}


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

using namespace std;

#define ll long long

ll dp[401][401];

bool v[401][401];

ll minMerge(ll i,ll j,ll* arr)

{

    if(i==j)

        return 0;

    if(v[i][j])

        return dp[i][j];

    v[i][j]=1;

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

    x=LONG_MAX;

    ll tot=0;

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

        tot+=arr[k];

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

    {

        x=min(x,tot+minMerge(i,k-1,arr)+minMerge(k,j,arr));

    }

    return x;

}

int main()

{

    ll n;

    cin>>n;

    ll arr[n+10];

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

    cout<<minMerge(0,n-1,arr);

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

#define ll long long

using namespace std;

const ll mod=1e9+7;

ll ps[100009],n,a[10009],dp[409][409];



ll f(ll l, ll r){

    if(l==r)return 0;

    ll tmp=1e17;

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

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

        tmp=min(tmp,f(l,i)+f(i+1,r)+ps[r]-ps[l-1]);

    }

    return dp[l][r]=tmp;

}



int main(){

    cin >> n;

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

        cin >> a[i];

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

    }

    memset(dp,-1,sizeof dp);

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

}

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

 

using namespace std;

 

long long MAX = 1e18 + 9 ;

#define mp make_pair

#define fi first

#define se second

#define pb push_back

#define vso(x) sort( x.begin() , x.end() )

#define aso(x) sort( x , x + x.size() )

#define print(x) cout << x << endl 

#define no cout << "NO\n" 

#define yes cout << "YES\n"

typedef long long ll ; 

typedef unsigned long long ull ;

typedef long double ld ;

typedef pair<ll, ll> pairs ;



ll a[500] , prefix[500] , x[500][500] ;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);

    cout.tie(NULL);

    //freopen("problem_name.out", "w", stdout) ;

    //freopen("problem_name.in", "r", stdin) ;

    //ull h ; cin >> h ; srand(h) ;

    //int t ; cin >> t ; while(t--){}

    ll n ; cin >> n ;

    ll sum = 0 ;

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

    {

        cin >> a[i] ;

        sum += a[i] ;

        prefix[i] = sum ;

    }



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

    {

        for ( ll j = 1 ; (j+i) <= n ; j++  )

        {

            ll mini = MAX ;

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

            {

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

            }

            x[j][(i+j)] = mini + ( prefix[(i+j)] - prefix[j-1] ) ;

            //cout <<  i << "  " << j << "  " << x[j][(i+j)] << "\n" ;

        }

    }

    print(x[1][n]) ;

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

using namespace std;



int const N=4e2+5, M=1e5+5, /*OO = 0x3f3f3f3f,*/ MOD=1e9+7;

long long const OO = 0x3f3f3f3f3f3f3f3f;

int n;

long long arr[N];



long long mem[N][N];

long long solve(int s, int e)

{

    if(s==e)

        return 0;

    if(mem[s][e]!=-1)

        return mem[s][e];

    long long ret=OO;

    for(int i=s; i<e; i++)

        ret=min(ret,solve(s,i)+solve(i+1,e)+arr[e]-arr[s-1]);

    return mem[s][e]=ret;

}





int main()

{

//    freopen("input.txt","rt",stdin);

//    freopen("output.txt","wt",stdout);

    scanf("%d",&n);



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

    {

        scanf("%lld",arr+i);

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

    }

    memset(mem, -1, sizeof mem);

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





}


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

 

using namespace std;

 

long long MAX = 1e18 + 9 ;

#define mp make_pair

#define fi first

#define se second

#define pb push_back

#define vso(x) sort( x.begin() , x.end() )

#define aso(x) sort( x , x + x.size() )

#define print(x) cout << x << endl 

#define no cout << "NO\n" 

#define yes cout << "YES\n"

typedef long long ll ; 

typedef unsigned long long ull ;

typedef long double ld ;

typedef pair<ll, ll> pairs ;



ll a[500] , prefix[500] , x[500][500] ;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);

    cout.tie(NULL);

    //freopen("problem_name.out", "w", stdout) ;

    //freopen("problem_name.in", "r", stdin) ;

    //ull h ; cin >> h ; srand(h) ;

    //int t ; cin >> t ; while(t--){}

    ll n ; cin >> n ;

    ll sum = 0 ;

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

    {

        cin >> a[i] ;

        sum += a[i] ;

        prefix[i] = sum ;

    }



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

    {

        for ( ll j = 1 ; (j+i) <= n ; j++  )

        {

            ll mini = MAX ;

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

            {

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

            }

            x[j][(i+j)] = mini + ( prefix[(i+j)] - prefix[j-1] ) ;

            //cout <<  i << "  " << j << "  " << x[j][(i+j)] << "\n" ;

        }

    }

    print(x[1][n]) ;

}
// Slower C++ solution:
//TINY_OUNCE911666

// You are not prepared!

 

#include <bits/stdc++.h>

using namespace std;

 

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }

template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {

  while(*sdbg!=',')cerr<<*sdbg++;

  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);

}

#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;



const int N = 407;

const ll INF = 1e18L+7;



int32_t main() {

	_upgrade

	

	int n; cin >> n;

	vector<int> a(n);

	for (int& x : a) {

		cin >> x;

	}

	

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

	

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

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

			if (r == l) {

				dp[l][r] = 0;

			}

			else {

				dp[l][r] = INF;

				

				ll sum = 0;

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

					sum += a[i];

				}

				

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

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

				}

			}

		}

	}

	

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

}


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

 

using namespace std;

 

long long MAX = 1e18 + 9 ;

#define mp make_pair

#define fi first

#define se second

#define pb push_back

#define vso(x) sort( x.begin() , x.end() )

#define aso(x) sort( x , x + x.size() )

#define print(x) cout << x << endl 

#define no cout << "NO\n" 

#define yes cout << "YES\n"

typedef long long ll ; 

typedef unsigned long long ull ;

typedef long double ld ;

typedef pair<ll, ll> pairs ;



ll a[500] , prefix[500] , x[500][500] ;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);

    cout.tie(NULL);

    //freopen("problem_name.out", "w", stdout) ;

    //freopen("problem_name.in", "r", stdin) ;

    //ull h ; cin >> h ; srand(h) ;

    //int t ; cin >> t ; while(t--){}

    ll n ; cin >> n ;

    ll sum = 0 ;

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

    {

        cin >> a[i] ;

        sum += a[i] ;

        prefix[i] = sum ;

    }



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

    {

        for ( ll j = 1 ; (j+i) <= n ; j++  )

        {

            ll mini = MAX ;

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

            {

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

            }

            x[j][(i+j)] = mini + ( prefix[(i+j)] - prefix[j-1] ) ;

            //cout <<  i << "  " << j << "  " << x[j][(i+j)] << "\n" ;

        }

    }

    print(x[1][n]) ;

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

#define pb push_back

#define x first 

#define y second

#define vec vector

#define ll long long

#define mp make_pair

#define pii pair<ll ,ll >

#define THICC 6942091166600000

#define speedup ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

#define loop(it) for(auto it = mep.begin();it!=mep.end();++it)

using namespace std;

int main(){

    int n;

    cin>>n;

    vector<ll> arr(420);

	vector<ll> pref(420);

    vector<vector<ll>> dp(666,vector<ll>(420 , 0));

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

		cin>>arr[i];

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

	}

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

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

			int l = j , r = j+i;

			dp[l][r] = THICC;

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

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

			}

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

        }

	}

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

}

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

 

using namespace std;

 

long long MAX = 1e18 + 9 ;

#define mp make_pair

#define fi first

#define se second

#define pb push_back

#define vso(x) sort( x.begin() , x.end() )

#define aso(x) sort( x , x + x.size() )

#define print(x) cout << x << endl 

#define no cout << "NO\n" 

#define yes cout << "YES\n"

typedef long long ll ; 

typedef unsigned long long ull ;

typedef long double ld ;

typedef pair<ll, ll> pairs ;



ll a[500] , prefix[500] , x[500][500] ;



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);

    cout.tie(NULL);

    //freopen("problem_name.out", "w", stdout) ;

    //freopen("problem_name.in", "r", stdin) ;

    //ull h ; cin >> h ; srand(h) ;

    //int t ; cin >> t ; while(t--){}

    ll n ; cin >> n ;

    ll sum = 0 ;

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

    {

        cin >> a[i] ;

        sum += a[i] ;

        prefix[i] = sum ;

    }



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

    {

        for ( ll j = 1 ; (j+i) <= n ; j++  )

        {

            ll mini = MAX ;

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

            {

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

            }

            x[j][(i+j)] = mini + ( prefix[(i+j)] - prefix[j-1] ) ;

            //cout <<  i << "  " << j << "  " << x[j][(i+j)] << "\n" ;

        }

    }

    print(x[1][n]) ;

}