stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;

}

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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



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

	return 0;

}


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





}


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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



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

	return 0;

}


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

}


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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



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

	return 0;

}


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

}

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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



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

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

/*                   وتزودوا فإن خير الزاد التقوى                    */

/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */

#include <bits/stdc++.h>

#include<unordered_map>

using namespace std;

#define endl '\n'

#define ll long long

#define PI acos(-1)

#define watch(x) cerr<<#x<<" = { "<<x<<" }\n"

#define sz(n) n.size();

#define Mo7med_Sayed fast();

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

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

#define RT(v) return cout<<v,0;

const double EPS = (1e-7);

const ll OO = INT_MAX, mod = 1e9 + 7;

void run() {

#ifndef ONLINE_JUDGE

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

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

#else

#endif

}

void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll n, m, k, t;

vector<ll>v;

ll dp[500][500];

ll solve(int l, int r) {

	if (l == r)return 0;

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

	if (~ret)return ret;

	ret = 1e17;

	ll s= (l ? v[l - 1] : 0);

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

		ret = min(ret, solve(l, i) + solve(i + 1, r) + (v[r] - s));

	}

	return ret;

}

int main()

{

	//run();

	Mo7med_Sayed;

	cin >> n;

	v.resize(n);

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

		cin >> v[i];

		v[i] += (i ? v[i - 1] : 0);

	}

	memset(dp, -1, sizeof dp);

	RT(solve(0, n -1));

}


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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



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

	return 0;

}


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

#include<algorithm>

#include<queue>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<cmath>

#include<ctime>



using namespace std;

const int maxn = 1e5 + 7;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const double pi = acos(-1.0);

typedef long long ll;

#define pb push_back



int n;

ll a[405];

ll dp[405][405];

ll sum[405][405];



int main(){

	scanf("%d", &n);

	memset(dp, inf, sizeof dp);

	memset(sum, 0, sizeof sum);

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

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

		dp[i][i] = 0;

		sum[i][i] = a[i];

	}

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

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

			int j = i + len;

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

				sum[i][j] = sum[i][k] + sum[k+1][j];

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

			}

		}

	}

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

}

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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

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

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

created by sanyam singhal

*/



#include<bits/stdc++.h>

using namespace std;



#define pb push_back

#define mp make_pair

#define ll long long int

#define mod 1000000007

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

#define triplet pair<int,pair<int,int>>

#define vi vector<int>

#define vll vector<ll>

#define pi pair<int,int>

#define pll pair<ll,ll>

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

#define loop(i, k, n) for(ll i=k; i<n; i+=1)

#define loop2(i, k, n) for(ll i=k; i>=n; i--)



const ll inf = 1e18;

const int N = 500;



ll dp[N][N];

ll sumij[N][N];



void take_fileIO(){

  #ifndef ONLINE_JUDGE

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

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

  #endif

  return;

}



ll solve_by_dp(vector<ll> &a, ll i, ll j){

  if(j==i){

    return 0;

  }

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

    return dp[i][j];

  else{

    ll ans = LLONG_MAX;

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

      ll part1 = solve_by_dp(a, i, k-1);

      ll part2 = solve_by_dp(a, k, j);

      ll curr_ans = part1 + part2 + sumij[i][k-1] + sumij[k][j];

      // cout<<curr_ans<<endl;

      if(curr_ans < ans){

        ans = curr_ans;

      }

    }

    return dp[i][j] = ans;

  }

}



void solve(){

  ll n; cin>>n;

  vector<ll>a(n);

  loop(i, 0, n) 

    cin>>a[i];



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

  // loop(i, 0, n)

  //   cout<<a[i]<<" ";



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

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

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

        sumij[i][j] += a[k];

      }

    }

  }



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

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

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

  //   }

  //   cout<<endl;

  // }



  cout<<solve_by_dp(a, 0, n-1)<<endl;

  return;

}



int main(){



  fastIO;

  // take_fileIO();

  solve();

  return 0;

}

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

using namespace std;



#define ll long long

#define pb push_back

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

#define mod 1000000007

#define inf (1LL<<60)

 

ll sum[401][401];

ll dp[401][401];

 

ll solve(vector<int>&arr,int i,int j){

    //base case

    if(i==j)

    return 0;

    //lookup

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

    return dp[i][j];

      ll mincost=inf;

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

    {

mincost=min(mincost,sum[i][j]+solve(arr,i,k)+solve(arr,k+1,j));

    }

 

 

return dp[i][j]=mincost;

}

 

void prepocess(vector<int>&arr,int n)

{

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

    {

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

        {

            sum[i][j]=arr[j]+((j==i)?0:sum[i][j-1]);

        }

    }

}

 

int main()

{ int n;

    cin>>n;

    // cout<<n;

    vector<int>arr(n+1);

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

   

    fr(1,n)

    cin>>arr[i];

    prepocess(arr,n);

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

    return 0;

 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

created by sanyam singhal

*/



#include<bits/stdc++.h>

using namespace std;



#define pb push_back

#define mp make_pair

#define ll long long int

#define mod 1000000007

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

#define triplet pair<int,pair<int,int>>

#define vi vector<int>

#define vll vector<ll>

#define pi pair<int,int>

#define pll pair<ll,ll>

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

#define loop(i, k, n) for(ll i=k; i<n; i+=1)

#define loop2(i, k, n) for(ll i=k; i>=n; i--)



const ll inf = 1e18;

const int N = 500;



ll dp[N][N];

ll sumij[N][N];



void take_fileIO(){

  #ifndef ONLINE_JUDGE

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

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

  #endif

  return;

}



ll solve_by_dp(vector<ll> &a, ll i, ll j){

  if(j==i){

    return 0;

  }

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

    return dp[i][j];

  else{

    ll ans = LLONG_MAX;

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

      ll part1 = solve_by_dp(a, i, k-1);

      ll part2 = solve_by_dp(a, k, j);

      ll curr_ans = part1 + part2 + sumij[i][k-1] + sumij[k][j];

      // cout<<curr_ans<<endl;

      if(curr_ans < ans){

        ans = curr_ans;

      }

    }

    return dp[i][j] = ans;

  }

}



void solve(){

  ll n; cin>>n;

  vector<ll>a(n);

  loop(i, 0, n) 

    cin>>a[i];



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

  // loop(i, 0, n)

  //   cout<<a[i]<<" ";



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

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

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

      //   sumij[i][j] += a[k];

      // }

      if(i==j){

        sumij[i][j] = a[j];

        continue;

      }

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

    }

  }



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

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

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

  //   }

  //   cout<<endl;

  // }



  cout<<solve_by_dp(a, 0, n-1)<<endl;

  return;

}



int main(){



  fastIO;

  // take_fileIO();

  solve();

  return 0;

}

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

using namespace std;



#define ll long long

#define pb push_back

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

#define mod 1000000007

#define inf (1LL<<60)

 

ll sum[401][401];

ll dp[401][401];

 

ll solve(vector<int>&arr,int i,int j){

    //base case

    if(i==j)

    return 0;

    //lookup

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

    return dp[i][j];

      ll mincost=inf;

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

    {

mincost=min(mincost,sum[i][j]+solve(arr,i,k)+solve(arr,k+1,j));

    }

 

 

return dp[i][j]=mincost;

}

 

void prepocess(vector<int>&arr,int n)

{

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

    {

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

        {

            sum[i][j]=arr[j]+((j==i)?0:sum[i][j-1]);

        }

    }

}

 

int main()

{ int n;

    cin>>n;

    // cout<<n;

    vector<int>arr(n+1);

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

   

    fr(1,n)

    cin>>arr[i];

    prepocess(arr,n);

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

    return 0;

 

}

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

#define ll long long int

#define ld long double

#define pb push_back

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

#define ff first

#define ss second

#define mod 1000000007

using namespace std;



ll dp[401][401];

vector<int> a;

ll slime(int l,int r){

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

	if(ans!=-1)

		return dp[l][r];

	if(r==l)

		return 0;

	ans = 1e15;

	ll rt = 0,lt = 0;

	for(int k=r;k>=l;--k)

		rt+=a[k];

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

		lt+=a[k];

		rt-=a[k];

		ans = min(slime(l,k)+slime(k+1,r)+lt+rt,ans);

	}

	return ans;

}



int main(){

	ios_base::sync_with_stdio(false); 

	cin.tie(NULL);cout.tie(NULL);

	int n;

	cin>>n;

	memset(dp,-1,sizeof dp);

	a.resize(n);

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

	{

		cin>>a[i];

	}

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

	// cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;

	return 0;

}

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

#define ll long long int

#define ld long double

#define pb push_back

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

#define ff first

#define ss second

#define mod 1000000007

using namespace std;



int main(){

	ios_base::sync_with_stdio(false); 

	cin.tie(NULL);cout.tie(NULL);

	int n;

	cin>>n;

	vector<int> a(n);

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

	{

		cin>>a[i];

	}

	vector<vector<ll> > dp(n,vector<ll> (n,1e15));

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

		dp[i][i]=0;

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

		for(int l=0;l+d<n;++l){

			int r=l+d;

			ll sum = 0;

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

				sum+=a[k];

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

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

			}

		}

	}

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

	// cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;

	return 0;

}

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

#include <vector>

#include <algorithm>

#include <limits>

using namespace std;



#define chmin(x, y) x = min(x, y)



// 入力

int n;

vector<long long> a;

// dp[left][right] := 区間 [left,right) におけるコストの最小値

vector<vector<long long>> dp(405, vector<long long>(405, -1));

// スライムの大きさの累積和

long long S[405];



// メモ化再帰

long long memo_rec(int left, int right){

    if(dp[left][right] != -1)   return dp[left][right];

    if(right - left == 1)   return dp[left][right] = a[left];



    long long res = numeric_limits<long long>::max();

    for(int pos = left + 1; pos < right; ++pos){

        long long tmp = 0;

        if(pos - left > 1)  tmp += memo_rec(left, pos) + S[pos] - S[left];

        else    tmp += memo_rec(left, pos);

        if(right - pos > 1) tmp += memo_rec(pos, right) + S[right] - S[pos];

        else    tmp += memo_rec(pos, right);

        chmin(res, tmp);

    }

    return dp[left][right] = res;

}



int main(){

    cin >> n;

    a.resize(n);

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

        cin >> a[i];

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

    }

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

}

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

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <string>

#include <map>

#include <set>

#include <stack>

#include <tuple>

#include <deque>

#include <numeric>

#include <bitset>

#include <iomanip>

#include <cassert>

#include <chrono>

#include <random>

#include <limits>

#include <iterator>

#include <functional>

#include <sstream>

#include <complex>

using namespace std;



using ll = long long;

using ull = uint64_t;

using P = pair<int, int>;

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



template<class T>

inline bool chmax(T& x, T y){

    if(x < y){

        x = y;

        return true;

    }

    return false;

}

template<class T>

inline bool chmin(T& x, T y){

    if(x > y){

        x = y;

        return true;

    }

    return false;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    int N;

    cin >> N;

    vector<int> a(N);

    vector<ll> S(N + 1);

    S[0] = 0;

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

        cin >> a[i];

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

    }



    constexpr ll inf = 1e+15;

    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, -1));

    auto MemoRec = [&](auto&& self, int l, int r) -> ll {

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

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



        ll res = inf;

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

            chmin(res, self(self, l, m) + self(self, m, r));

        }

        res += S[r] - S[l];



        return dp[l][r] = res;

    };



    cout << MemoRec(MemoRec, 0, N) << endl;

}

// Fastest known solution for this problem: