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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

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

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


// Faster C++ solution for the same problem (measured speedup: 1.1014589547914717x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

using namespace std;

//<DEFINE>

void Fast() {

	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

}

void File() {

#ifndef ONLINE_JUDGE

	freopen("Input.txt", "r", stdin);

	freopen("Output.txt", "w", stdout);

#endif

}

#ifdef _MSC_VER

#include <intrin.h>

#define __builtin_popcount __popcnt

#ifdef _WIN64

#define __builtin_popcountll __popcnt64

#else

inline int __builtin_popcountll(__int64 a) {

	return __builtin_popcount((unsigned int)a) + __builtin_popcount(a >> 32);

}

#endif

#endif

using ll = long long;

using ull = unsigned long long;

#define mod 1000000007

ll gcd(ll a, ll b) {

	return!b ? a : gcd(b, a % b);

}

#define fix(n) cout << fixed << setprecision(n);

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

#define skip continue

#define stop(n) return cout<<n,0

#define pi  acos(-1)

#define endl "\n"

//#define ceil(x,y) ((x+y-1)/y)

//sin(x*pi/180)

//alot of memset may cause TLE

#define TC int t;cin>>t;while(t--)

//</DEFINE>

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

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

ll n, slime[401];

ll res[401][401];

//<FUNCTIONS>

ll solve(int l = 1, int r = n ) {

	ll& mn = res[l][r];

	if (~mn)return mn;

	if (l == r)return 0;

	mn = 1e18;

	ll x, y;

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

		mn = min(mn, solve(l, i - 1) + slime[i - 1] - slime[l - 1] + solve(i, r) + slime[r] - slime[i - 1]);

	}

	return mn;

}

//</FUNCTIONS>	

int main() {

	Fast();

	cin >> n;

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

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

	}

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

	cout << solve();

}
// Slower C++ solution:
// Ivan Carvalho

// Problem N - Educational Dynamic Programming Contest - AtCoder

// Link : https://atcoder.jp/contests/dp

#include <bits/stdc++.h>

using namespace std;



typedef long long ll;



const int MAXN = 410;

const ll INF = 1e14;



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

int N;



ll calc(ll a,ll b){

	if(a > b) return INF;

	return pref[b] - pref[a-1];

}



ll solve(int ini,int fim){

	if(dp[ini][fim] != -1) return dp[ini][fim];

	if(ini == fim) return dp[ini][fim] = 0;

	if(ini + 1 == fim) return dp[ini][fim] = V[ini] + V[fim];



	ll best = INF;



	for(int i = ini;i<fim;i++){

		ll cand = solve(ini,i) + solve(i+1,fim) + calc(ini,fim);

		best = min(best,cand);

	}



	return dp[ini][fim] = best;



}



int main(){



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



	cin >> N;

	for(int i = 1;i<=N;i++) cin >> V[i];



	for(int i = 1;i<=N;i++) pref[i] = pref[i-1] + V[i];



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



	return 0;



}

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

using namespace std ;

#define  ll long long int 

#define pb push_back 



vector<ll> sss , dd;

ll arr[401][401] , visi[401][401] ;

ll sum(ll i , ll j)

{

    if(i!=0)

    return sss[j] -sss[i-1] ;

    

    return sss[j] ;

}





ll solve(ll i , ll j )

{

    if(i==j){

        

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

    

    return 0 ;

    }

    if(j-i==1)

    {

        

//    cout<< i<<"  "<< j<<"  " << sum(i,j)  <<endl ;

    

        return sum(i,j) ;

    }

    if(visi[i][j] ==1 )

    {

        

        return arr[i][j] ;

    }

    

    

    

    ll m =10000000000000 ;

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

    {

        m = min(m , solve(i, h) +solve(h+1 , j) ) ;

        

  //      cout<<  i <<"  "<<h  << "  "<< h+1 <<"  " << j << "  sum" << "  "<<solve(i , h)  << "  " << solve(h+1 , j ) << endl ;

        

        

        

    }

    m+=sum(i , j)  ;

    

    visi[i][j] =1 ;

    arr[i][j] = m ;

    

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

    return m ;

    

    

    

}



int main()

{

     ll n ;

     cin >> n ;

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

     {

         ll l ;

         cin >> l ;

         dd.pb(l) ;

     }

     

     sss.pb(dd[0] ) ;

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

     {

         sss.pb(sss[i-1] + dd[i]) ;

     }

     

     

     cout<<solve(0,n-1) ;

     return 0 ;

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



using namespace std;

using ll = long long;



using Field = vector<vector<int>>;

using Graph = vector<vector<int>>;

using VI = vector<int>;

using VC = vector<char>;

using PI = pair<int, int>;



#define REP(i, n) for (int i = 0; i < (n); i++)

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



const long long INF = 1LL<<60;

const int mod = 1000000007;



template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }



int N;

vector<ll> A;

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





int main() {

    cin.tie(0);

    ios_base::sync_with_stdio(false);



    cin >> N;

    A.resize(N + 1, 0);

    REP(i, N) cin >> A.at(i);



    REP(i, N) dp.at(i).at(i) = 0;



    for (int len = 1; len < N; len++) {

        for (int left = 0; left < N - len; left++) {

            ll tmp = INF;

            ll sum = 0;

            int right = left + len;

            for (int idx = left; idx < right; idx++) {

                tmp = min(tmp, dp.at(left).at(idx) + dp.at(idx + 1).at(right));

                sum  += A.at(idx);

            }

            sum += A.at(right);

            dp.at(left).at(right) = tmp + sum;



        }

    }



    cout << dp.at(0).at(N - 1) << endl;



    

    return 0;

}

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



using namespace std;

using ll = long long;



using Field = vector<vector<int>>;

using Graph = vector<vector<int>>;

using VI = vector<int>;

using VC = vector<char>;

using PI = pair<int, int>;



#define REP(i, n) for (int i = 0; i < (n); i++)

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



const long long INF = 1LL<<60;

const int mod = 1000000007;



template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }



int N;

vector<ll> a;

vector<vector<ll>> dp;

vector<ll> S;



int main() {

    cin.tie(0);

    ios_base::sync_with_stdio(false);



    cin >> N;

    a.resize(N);

    S.resize(N + 1);

    REP(i, N) cin >> a[i];

    dp.assign(N + 1, vector<ll>(N + 1, INF));



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

        dp[i][i] = 0;

    }



    S[0] = 0;

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

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

    }



    for (int len = 1; len < N; len++) {

        for (int l = 0; l + len <= N; l++) {

            int r = l + len;

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

                chmin(dp[l][r], dp[l][m] + dp[m + 1][r] + S[r + 1] - S[l]);

            }

        }

    }



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

    

    return 0;

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

#define lli long long

using namespace std;



vector<long long>vp;



long long dp[410][410];

long long dpp(int i,int j)



{

  if(i>j)

  return 0;

  if(j==i)

  return 0;



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

  return dp[i][j];



 long long ans=1e20;

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

  {

    ans=min(ans,vp[j]-vp[i-1]+dpp(i,x)+dpp(x+1,j));

  }



return dp[i][j]=ans;

}

int main()

{



    memset(dp,-1,sizeof dp);

    int n;

    cin>>n;

    long long sum=0;

    vp.push_back(0);

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

    {

      int a;

      cin>>a;

      sum+=a;

      vp.push_back(sum);



    }

    cout <<dpp(1,n);

}










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



using namespace std;

long long dp[405][405],s[405],a[405],i,j,k,n;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

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

    }

    for(k=1;k<n;k++)

    {

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

        {

            dp[i][i+k]=a[i]+dp[i+1][i+k]+s[i+k]-s[i];

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

            {

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

            }

        }

    }

    cout<<dp[1][n];

    return 0;

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

using namespace std;

long long n,a[410],dp[410][410],pref[410];

long long f(long long l,long long r)

{

//	printf("%lld %lld\n",l,r);

	if(r<=l || l>=r) return 0;

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

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

	{

	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);

		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 

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

	}

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

}

int main()

{

	scanf("%lld",&n);

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

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

	{

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

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

	}	

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

//	printf("c : \n");

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

//	{

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

//		{

//			printf("%d %d %lld\n",i,j,dp[i][j]);

//		}

//	}

	return 0;

}

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



using namespace std;

long long dp[405][405],s[405],a[405],i,j,k,n;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

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

    }

    for(k=1;k<n;k++)

    {

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

        {

            dp[i][i+k]=a[i]+dp[i+1][i+k]+s[i+k]-s[i];

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

            {

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

            }

        }

    }

    cout<<dp[1][n];

    return 0;

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 4e2+5;



const int mod = 1e9+7;



int n;

int ar[N];

long long prefix[N];

long long mem[N][N];



long long getsum(int l , int r){

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

}



long long go(int l , int r){

    if(r - l + 1 == 2)

        return getsum(l , r);

    if(l >= r)

        return 0;

    if(~mem[l][r])

        return mem[l][r];

    long long best = 1e18;

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

        best = min(best , go(l , i) + go(i + 1 , r) + getsum(l , i) + getsum(i + 1 , r));

    }

    return mem[l][r] = best;

}



int main(){

    scanf("%d" , &n);

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

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

        prefix[i] = ar[i] + prefix[i - 1];

    }

    memset(mem , -1 , sizeof mem);

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

}


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



using namespace std;

long long dp[405][405],s[405],a[405],i,j,k,n;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

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

    }

    for(k=1;k<n;k++)

    {

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

        {

            dp[i][i+k]=a[i]+dp[i+1][i+k]+s[i+k]-s[i];

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

            {

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

            }

        }

    }

    cout<<dp[1][n];

    return 0;

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

using namespace std;

const int N = 2e4 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;

const long long OO = 1e18+25;

#define par pair<pair<int,int>, int>

#define f first

#define s second



int n, a[405];

long long mem[405][405],cum[405];



long long dp(int start=1, int end=n)

{

    if(start == end) return 0;

    long long &ret =mem[start][end];

    if(~ret) return ret;

    ret = OO;

    for(int i=start; i<end; i++)

    {

        ret = min(ret,1ll* dp(start, i)+dp(i+1, end)+(cum[i]-cum[start-1])+(cum[end]-cum[i]));

    }

    return ret;

}



int main()

{

    memset(mem, -1, sizeof mem);

    scanf("%d",&n);

    for(int i=1; i<=n ;i++)scanf("%d",a+i);

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

    printf("%lld",dp());

    return 0;

}

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



using namespace std;

long long dp[405][405],s[405],a[405],i,j,k,n;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

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

    }

    for(k=1;k<n;k++)

    {

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

        {

            dp[i][i+k]=a[i]+dp[i+1][i+k]+s[i+k]-s[i];

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

            {

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

            }

        }

    }

    cout<<dp[1][n];

    return 0;

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

#define lli long long

using namespace std;



vector<long long>vp;



long long dp[410][410];

long long dpp(int i,int j)



{

  if(i>j)

  return 0;

  if(j==i)

  return 0;



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

  return dp[i][j];



 long long ans=1e20;

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

  {

    ans=min(ans,vp[j]-vp[i-1]+dpp(i,x)+dpp(x+1,j));

  }



return dp[i][j]=ans;

}

int main()

{



    memset(dp,-1,sizeof dp);

    int n;

    cin>>n;

    long long sum=0;

    vp.push_back(0);

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

    {

      int a;

      cin>>a;

      sum+=a;

      vp.push_back(sum);



    }

    cout <<dpp(1,n);

}










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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

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

using namespace std;

long long n,a[410],dp[410][410],pref[410];

long long f(long long l,long long r)

{

//	printf("%lld %lld\n",l,r);

	if(r<=l || l>=r) return 0;

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

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

	{

	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);

		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 

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

	}

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

}

int main()

{

	scanf("%lld",&n);

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

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

	{

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

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

	}	

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

//	printf("c : \n");

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

//	{

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

//		{

//			printf("%d %d %lld\n",i,j,dp[i][j]);

//		}

//	}

	return 0;

}

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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 4e2+5;



const int mod = 1e9+7;



int n;

int ar[N];

long long prefix[N];

long long mem[N][N];



long long getsum(int l , int r){

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

}



long long go(int l , int r){

    if(r - l + 1 == 2)

        return getsum(l , r);

    if(l >= r)

        return 0;

    if(~mem[l][r])

        return mem[l][r];

    long long best = 1e18;

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

        best = min(best , go(l , i) + go(i + 1 , r) + getsum(l , i) + getsum(i + 1 , r));

    }

    return mem[l][r] = best;

}



int main(){

    scanf("%d" , &n);

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

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

        prefix[i] = ar[i] + prefix[i - 1];

    }

    memset(mem , -1 , sizeof mem);

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

}


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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

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

using namespace std;

const int N = 2e4 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;

const long long OO = 1e18+25;

#define par pair<pair<int,int>, int>

#define f first

#define s second



int n, a[405];

long long mem[405][405],cum[405];



long long dp(int start=1, int end=n)

{

    if(start == end) return 0;

    long long &ret =mem[start][end];

    if(~ret) return ret;

    ret = OO;

    for(int i=start; i<end; i++)

    {

        ret = min(ret,1ll* dp(start, i)+dp(i+1, end)+(cum[i]-cum[start-1])+(cum[end]-cum[i]));

    }

    return ret;

}



int main()

{

    memset(mem, -1, sizeof mem);

    scanf("%d",&n);

    for(int i=1; i<=n ;i++)scanf("%d",a+i);

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

    printf("%lld",dp());

    return 0;

}

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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

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

using namespace std;

#define endl '\n'

long long arr[401];

int n;

long long dp[401][401];

long long f(int l,int r){

	if(l==r)return 0;

	long long &mi=dp[l][r];

	if(~mi)return mi;

	mi=1000000000000000000LL;

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

		mi=min(mi,f(l,i)+f(i+1,r)+arr[r]-arr[l-1]);

	}

	return mi;

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	memset(dp,-1,sizeof dp);



	cin>>n;

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

		cin>>arr[i];

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

	}





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



	return 0;

}

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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

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



using namespace std;



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

#define allr(v)				((v).rbegin()), ((v).rend())

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

#define ll long long

#define pb					push_back

#define fIO ios_base::sync_with_stdio(0);cin.tie(0);



const ll oo = 1e8;

const double pi = 3.1415926535897;





const double EPS = (1e-7);

int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}





typedef vector<int>                vi;

typedef vector<pair<int,int>>      vii;

typedef vector<ll>                 vll;

typedef vector<double>             vd;

typedef vector< vi >               vvi;

typedef vector< vd >               vvd;

typedef vector<string>             vs;

typedef pair<int, int>             pii;



/**

    * PLEASEEE READDD PROBLEEEM CARFULLY ****

    * Always check for OVERFLOW ll vs int

    * Always check for array bounds

    * Check for function return

    * READ OUTPUT SECTION AGAIN!!!

**/



struct edge{

    int from, to, w;



    edge(){}

    edge(int x, int y, int we): from(x), to(y), w(we){}



    bool operator < (const edge &rhs) const{

        return w > rhs.w;

    }



};



const int N = 400 + 5;



ll dp[N][N];

ll pre[N];

int a[N];



ll sol(int l ,int r) {

    if(l == r) return 0;



    ll &ret = dp[l][r];

    if(ret != -1) return ret;



    ret = 1e18L;

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

        ret = min(ret, sol(l, i) + sol(i + 1, r) + pre[r + 1] - pre[l]);

    }



    return ret;

}







int main(){

    fIO

//    freopen("", "r", stdin);

//    freopen("", "w", stdout);



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



    int n;

    cin >> n;



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



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



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

}














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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

}
// Slower C++ solution:


#include <iostream>

#include <climits>

#include <cstring>

#include <algorithm>



using namespace std;



#define SIZE 420

long long cost[SIZE][SIZE], a[SIZE];



long long minimalSum(int l, int r) {

    if (     l     >=  r) return 0;

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

    long long MIN = LLONG_MAX, sum = 0;

    for (int i = l; i <= r; i++) sum += a[i];

    for (int i = l; i <  r; i++) MIN = min(MIN, minimalSum(l  , i)

                                          +sum+ minimalSum(i+1, r));

    return cost[l][r] = MIN;

}



int main() {

    memset(cost, -1, sizeof cost);

    int N; cin >> N;

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

    cout << minimalSum(0, N-1) << endl;

    return 0;

}


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

using namespace std;

long long dp[401][401];

int main() {

	int n;

	cin>>n;

	vector < int > a(n);

	vector < long long > sum(n+1);

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

	sum[0]=0;

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

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

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

			dp[j][j + i]=1e18;

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

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

			}

		}

	}

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

	return 0;

}