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

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<queue>

#include<vector>

#include <bitset>

#include <cmath>

#include <limits>

#include <iostream>

#include<map>

#include<tuple>

using namespace std;

#define INF 1LL<<62

#define MAX 1100000

#define MOD 1000000007

typedef long long ll;

typedef pair<ll,ll> P;

typedef pair<pair<int,int>,int> p;

typedef pair< pair<int,int>, int> p; 

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/

#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

//__builtin_popcount(S)



//https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035



bool flag[410][410];

ll S[410],a[410];

ll dp[410][410];



ll f(int l,int r){

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

    flag[l][r]=true;

    if(l==r) return 0;

    ll fans=INF;

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

        fans=min(fans,f(l,m)+f(m+1,r));

    }

    return dp[l][r]=fans+S[r]-S[l-1];

}



int main(){

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

        for(int j=0;j<410;j++) flag[i][j]=false;

    }

    int N; cin>>N;

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

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

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

    }

    ll ans=f(1,N);

    cout<<ans<<endl;

}




// Optimized solution to the same problem (faster):
#pragma GCC optimize("Ofast")

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<queue>

#include<vector>

#include <bitset>

#include <cmath>

#include <limits>

#include <iostream>

#include <map>

#include<tuple>

using namespace std;

#define INF 1LL<<62

#define MAX 100000

#define MOD 1000000007

typedef long long ll;

typedef pair<int,int> P;

typedef pair<pair<int,int>,int> p;

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/

#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

struct edge{ll to,cost,val;};

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

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

//__builtin_popcount(S);

//C.erase(unique(C.begin(),C.end()),C.end());

//#define int ll



ll a[410],sum[410];

ll dp[410][410];



ll dfs(int r,int l){

    if(r==l) return 0;

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

    ll temp=INF;

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

        temp=min(dfs(r,x)+dfs(x+1,l)+sum[l]-sum[r-1],temp);

    }

    return dp[r][l]=temp;

}





signed main(){

    int N;

    cin>>N;

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

        cin>>a[i];

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

    } 

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







}

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

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

using namespace std;

using ll = long long;

const int INF = (1<<30)-1;

const long long LINF = (1LL<<62)-1;

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

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

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; }



const int MAX = 410;

ll dp[MAX][MAX];

vector<ll> a, sum;

ll dfs(int l, int r) {

  if (dp[l][r] >= 0)

    return dp[l][r];

  if (r-l == 1)

    return dp[l][r] = 0;

  ll res = LINF;

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

    chmin(res, dfs(l, i)+dfs(i, r));

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

}



signed main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  cin >> n;

  a.resize(n);

  rep(i, n) cin >> a[i];

  sum.resize(n+1, 0);

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

  rep(i, MAX) rep(j, MAX) dp[i][j] = -1;

  ll ans = dfs(0, n);

  cout << ans << endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

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

using namespace std;

using ll = long long;

const int INF = (1<<30)-1;

const long long LINF = (1LL<<62)-1;

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

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

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; }



signed main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  cin >> n;

  vector<int> a(n);

  rep(i, n) cin >> a[i];

  vector<vector<ll>> dp(n+1, vector<ll>(n+1, LINF));

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

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

  vector<ll> sum(n+1);

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

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

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

      ll res = LINF;

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

        chmin(res, dp[i][k]+dp[k][i+len]);

      dp[i][i+len] = res+sum[i+len]-sum[i];

    }

  }

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

  return 0;

}

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

using namespace std;



#define int long long 

#define f(i,n) for(int i=1;i<=n;i++)

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



const int N = 403;

const int inf = 1e15;



int dp[N][N];

int a[N];

int n;



int calc(int i,int j)

{

    if(i == j) return 0;

    

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

    

    assert(i < j);

    

    dp[i][j] = inf;

    

    for(int k=i;k<j;k++) dp[i][j] = min(dp[i][j], calc(i,k) + calc(k+1,j) + a[j] - a[i-1]);

    

    return dp[i][j];

}



void solve()

{

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

    

    cin >> n;

    

    f(i,n) cin >> a[i];

    

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

    

    cout << calc(1,n);

}



signed main()

{

    fast;

    solve();

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define int long long 

#define f(i,n) for(int i=1;i<=n;i++)

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



const int N = 403;

const int inf = 1e15;



int dp[N][N];

int a[N];

int n;



void solve()

{   

    cin >> n;

    

    f(i,n) cin >> a[i];

    

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

    

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

    {

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

        {

            dp[i][i+len] = inf;

            

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

                dp[i][i+len] = min(dp[i][i+len],dp[i][j] + dp[j+1][i+len] + a[i+len] - a[i-1]);

        }

    }

    

    cout << dp[1][n];

}



signed main()

{

    fast;

    solve();

}

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

using namespace std;



#define ll long long 

ll int pre[405];

ll int dp[405][405];



ll int kil(int l, int r)

{

    if(l == r)

        return 0;//pre[l] - pre[l-1];

        

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

        return dp[l][r];

        

    dp[l][r] = 1e17;

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

    {

        dp[l][r] = min(dp[l][r], pre[r] - pre[l-1] + kil(l, i) + kil(i+1, r));

    }

    return dp[l][r];    

}



int main()

{

    int n, x;

    cin>>n;

    

    memset(dp, -1, sizeof dp);

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

    {

        cin>>x;

        pre[i] = pre[i-1] + x;

    }

    

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

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#include <string>

#include <vector>

#include <typeinfo>

using namespace std;

#define ll long long 

 

int main()

{

    int n;

    cin>>n;

    ll pre[n];

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

        ll val;

        cin >> val;

        if (i > 0) {

            pre[i] = val + pre[i-1];

        }

        else {

            pre[i] = val;

        }

    }

    ll dp[n][n];

    fill(*dp, *dp + n*n, 0);

    

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

        for(int R = L; R<n; ++R) {

            if (L < R) {

                dp[L][R] = 1e15;

                for (int K=L; K<R; ++K){

                    ll rsum = pre[R];

                    if (L!=0) {

                        rsum = pre[R] - pre[L-1];

                    }

                    dp[L][R] = min(dp[L][R], dp[L][K] + dp[K+1][R] + rsum);

                }

            }

        }

    }

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

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

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

    //     cout << endl;

    // }

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

    return 0;

}


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

using namespace std;

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

typedef pair<ll,ll> pll;

const ll mod=1e9+7;

//const ll mod=998244353;

const ll inf=5e18;



ll n;

mat dp(410,vec(410,0));

vec a(410);



ll solve(ll l,ll r) {

  if(l==r) return 0;

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

  ll res=inf;

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

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

  }

  res+=a[r];

  if(l>0) res-=a[l-1];

  return dp[l][r]=res;

}



int main() {

  cin >> n;

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

    cin >> a[i];

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

  }

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

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

typedef pair<ll,ll> pll;

const ll mod=1e9+7;

//const ll mod=998244353;

const ll inf=1LL<<61;



int main() {

  ll n;

  cin >> n;

  vec a(n+1);

  for(ll i=1;i<=n;i++) cin >> a[i];

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

  mat dp(n,vec (n,inf));

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

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

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

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

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

      }

    }

  }

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

}

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

#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())

using namespace std;

int n;

long long a[500],q[500];

long long dp[500][500];

int main(){

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

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

	ios::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cin>>n;

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

		cin>>a[i];

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

	}

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

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

		dp[i][i]=0;

		dp[0][i]=0;

	}

	long long S;

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

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

			int j=i+l;

			S=q[j]-q[i-1];

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

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

			}

		}

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define STDIO

#define MOD 1000000007

#define testbit(mask,i) (((mask)>>(i))&1)

#define setbit(mask,i) ((mask)|(1<<i))

#define delbit(mask,i) ((mask)^(1<<i))

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

#define INF MOD

using namespace std;

int n;

long long a[420];

long long dp[420][420];

long long s[420];

int main(){

	#ifndef STDIO

		freopen("input.in","r",stdin);

		freopen("output.out","w",stdout);

	#endif

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	cin>>n;

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

		cin>>a[i];

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

	}

	long long S,j;

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

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

			j=i+l;

			S=s[j]-s[i-1];

			dp[i][j]=1e18;

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

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

			}

			dp[i][j]+=S;

		}

	}

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

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define pr(num) cout << num << "\n"

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 200010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;



ll N;

ll a[444];

ll dp[444][444];



ll rec(ll l, ll r) {

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

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

    

    ll res=INF;

    ll sum=0;

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

        sum+=a[i];

    }

    

    for(ll mid=l+1; mid<r; mid++) {

        res=min(res, rec(l, mid)+rec(mid, r)+sum);

    }

    

    return dp[l][r]=res;

}



int main() {

    cin >> N;

    

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

    

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

        cin >> a[i];

    }

    

    pr(rec(0, N));

    

    

    

    

    

}
























// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ft first

#define sc second

#define pt(sth) cout << sth << "\n"

#define chmax(a, b) {if(a<b) a=b;}

#define chmin(a, b) {if(a>b) a=b;}

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const ll INF=1e18;

static const ll MAX=101010;

static const ll MOD=1e9+7;



ll N;

ll a[444];

ll s[444];

ll mem[444][444];

ll rec(ll l, ll r) {

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

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

  

  

  ll res=INF;

  for(ll m=l+1; m<r; m++) {

    chmin(res, rec(l, m)+rec(m, r)-s[l-1]+s[r-1]);

  }

  

  return mem[l][r-1]=res;

}



int main() {

  cin >> N;

  ll i, j;

  

  for(i=1; i<=N; i++) {

    cin >> a[i];

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

  }

  

  memset(mem, -1, sizeof(ll));

  for(i=1; i<N+1; i++) {

    for(j=1; j<N+1; j++) {

      mem[i][j]=-1;

    }

  }

  

  pt(rec(1, N+1));

  

}














// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;



ll N;

ll mem[404][404]={};

ll a[MAX];



ll rec(ll l, ll r) {

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

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

    

    ll res=INF;

    ll sum=0;

    

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

    

    for(ll mid=l+1; mid<r; mid++) {

        res=min(res, rec(l, mid)+rec(mid, r)+sum);

    }

    

    return mem[l][r]=res;

}



int main(void) {

    cin >> N;

    ll i;

    

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

    

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

    pt(rec(0, N));

    

}




// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ft first

#define sc second

#define pt(sth) cout << sth << "\n"

#define chmax(a, b) {if(a<b) a=b;}

#define chmin(a, b) {if(a>b) a=b;}

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

static const ll INF=1e18;

static const ll MAX=101010;

static const ll MOD=1e9+7;



ll N;

ll a[444];

ll s[444];

ll mem[444][444];

ll rec(ll l, ll r) {

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

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

  

  

  ll res=INF;

  for(ll m=l+1; m<r; m++) {

    chmin(res, rec(l, m)+rec(m, r)-s[l-1]+s[r-1]);

  }

  

  return mem[l][r-1]=res;

}



int main() {

  cin >> N;

  ll i, j;

  

  for(i=1; i<=N; i++) {

    cin >> a[i];

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

  }

  

  memset(mem, -1, sizeof(ll));

  for(i=1; i<N+1; i++) {

    for(j=1; j<N+1; j++) {

      mem[i][j]=-1;

    }

  }

  

  pt(rec(1, N+1));

  

}














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

using namespace std;

#define ll long long

#define ll_s long

#define mod 1000000007

#define forn(i,start,lim) for(ll i=start;i<lim;i++)

#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)

#define f first

#define s second

#define pb push_back

#define pf push_front

#define mp make_pair

#define debug1(a) cout<<a<<endl

#define debug2(a,b) cout<<a<<" "<<b<<endl

#define debug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl

#define debug4(a) cout<<"chu "<<a<<endl

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

#define endl "\n"



ll memo[405][405];

ll sum[405];



ll fn(ll i,ll j){

  if(i==j) return 0;

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

    return memo[i][j];

  ll ans=1e18;

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

    ll cost=sum[j]-sum[i-1];

    ans=min(ans,fn(i,k)+fn(k+1,j)+cost);

  }

  memo[i][j]=ans;

  return ans;

}



int main()

{

  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  ll n,x;

  cin>>n;

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

  forn(i,1,n+1){

    cin>>x;

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

  }

  ll ans=fn(1,n);

  cout<<ans<<endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define ll_s long

#define mod 1000000007

#define forn(i,start,lim) for(ll i=start;i<lim;i++)

#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)

#define f first

#define s second

#define pb push_back

#define pf push_front

#define mp make_pair

#define debug1(a) cout<<"------\n"<<#a<<" = "<<a<<endl<<"------"<<endl

#define debug2(a,b) cout<<"--------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<endl<<"--------------"<<endl

#define debug3(a,b,c) cout<<"----------------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<" ; "<<#c<<" = "<<c<<endl<<"----------------------"<<endl

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

#define debug4(a) cout<<"chu "<<a<<endl

#define endl "\n"



ll n,presum[405],a[405],dp[405][405];



ll PreSum(ll l,ll r){

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

}



int main()

{

  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n;

	forn(i,1,n+1){

		cin>>a[i];

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

	}

	for(ll l=n;l>=1;l--){

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

			if(l==r)

				dp[l][r]=0;

			else{

				dp[l][r]=1e18;

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

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

				}

			}

		}

	}

	ll ans=dp[1][n];

	cout<<ans<<endl;

	return 0;

}


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

using namespace std;

typedef long long int lli;

lli dp[401][401];

/*This function is used to give the

sum of colours from a to be

after taking mod by 100*/



lli Sum(lli val[],lli a,lli b)

{

   lli sumv=0;

   for(lli i=a;i<=b;++i)

      sumv=sumv+val[i];

   return sumv;

}

/*This approach is very much similar to matrix chain multipliaction, where

we minimize the number of products/multiplications. Here we calculate the

residual smoke from both sides and then use this for storing the product.

dp[a][b] contains the value of product */

lli HarryMatMul(lli val[],lli a,lli b)

{

   if(dp[a][b]!=-1)

      return dp[a][b];

   else if(a==b)

   {

      dp[a][b]=0;

      return 0;

   }

   lli temp;

      for(lli k=a;k<b;++k)

      {

         temp=HarryMatMul(val,a,k)+HarryMatMul(val,k+1,b)

         +Sum(val,a,k)+Sum(val,k+1,b);



         if(dp[a][b]==-1||temp<dp[a][b])

            dp[a][b]=temp;

      }

      //for(int i=--0;i<)

      return dp[a][b];

}

int main() {

   lli n;

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

 cin>>n;

  // {

      lli val[n];

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

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

         cin>>val[i];

      cout<<HarryMatMul(val,0,n-1);//

      //printf("%d\n",HarryMatMul(val,0,n-1));

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

      {

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

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

          cout<<"\n";

      }*/

  // }

   return 0;

}


// Optimized solution to the same problem (faster):
//1.read question_2.read I/O_3.read test cases_4.read constraints(to decide TC of solution)_5.decide method_6.dry run_

//7.code_8.test_9.submit

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define mod 1000000007

#define F first

#define S second

#define _READ freopen("input.txt","r", stdin);

#define pb push_back

#define MP make_pair

#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main()

{

   

    _FAST

    lli n,t,i,j,k,ans=0,flag=0,a,b,m;

    cin>>n;vector<lli> ar(n);

    for(auto &i:ar)

        cin>>i;

    vector<vector<lli>> dp(n,vector<lli>(n,LONG_LONG_MAX));

    //dp[i][j]- min costin comnbining from i to j

    vector<lli> prefixSum(n+1,0);

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

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

    for(i=n-1;i>=0;i--)

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

        if(i==j)

        dp[i][j]=0;

        else

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

                dp[i][j]=min(dp[i][k]+dp[k+1][j]+prefixSum[j+1]

                             -prefixSum[i],

                        dp[i][j]);

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

    return 0;

}


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

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

#define line cout<<"----------------------"<<endl

#define mp make_pair

#define mod 1000000007

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

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll  mx=2000009;

ll ara[mx];

ll dp[409][409];

ll sum[409];

int main()

{

    ll n;

    cin>>n;

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

    {

        cin>>ara[i];

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

    }

    for(ll i=n;i>0;i--)

    {

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

        {

            dp[i][j]=LLONG_MAX;

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

            {

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

            }

        }

    }

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



}


// Fastest known solution for this problem: