stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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));

}


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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

	if(l + 1 == r) return a[l] + a[r];

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

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

	return 0;

}
// Slower C++ solution:
#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]);

}

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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

	if(l + 1 == r) return a[l] + a[r];

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

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

	return 0;

}
// Slower C++ solution:
/*

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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3164320483597085x):
#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;

 

}
// Slower C++ solution:
/*

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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3164351366057543x):
#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;

 

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.2578782528719077x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.3296414271286965x):
#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;



typedef long long ll;

typedef uint64_t ull;

typedef pair<int, int> P;

constexpr double PI = 3.1415926535897932;   // acos(-1)

constexpr double EPS = 1e-9;

constexpr int INF = 1001001001;

constexpr int mod = 1000000007;

// constexpr int mod = 998244353;



#define chmax(x, y) x = max(x, y)

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



int n;

vector<int> a;

vector<ll> S;

vector<vector<ll>> dp;



ll memo_rec(int Left = 0, int Right = n){

    if(dp[Left][Right] != -1)   return dp[Left][Right];

    if(Right - Left == 1)   return dp[Left][Right] = 0;



    ll res = 1e+15;

    ll Size = S[Right] - S[Left];

    for(int i = Left + 1; i < Right; ++i){

        ll sum = Size + memo_rec(Left, i) + memo_rec(i, Right);

        chmin(res, sum);

    }



    return dp[Left][Right] = res;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);



    cin >> n;

    a.resize(n);

    S.resize(n + 1);

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

    S[0] = 0;

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

        cin >> a[i];

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

    }

    cout << memo_rec() << endl;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.334412070050354x):
#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;

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

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

#define PI 3.141592653589793238462643383279502884L

#define lli long long int

#define d double

#define mod 1000000007

#define mx 100001

using namespace std;

lli dp[401][401];//dp[l][r]->min cost to mashup from range i to j....

lli sum[401][401];

lli fun(vector<int>&vec,int l,int r){

	if(l>=r) return 0;

	if(r-l==1) return vec[l]+vec[r];

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

	lli ans=99999999999999999;

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

		ans=min(ans,fun(vec,l,i)+fun(vec,i+1,r)+sum[l][r]);

	}

	return dp[l][r]=ans;

}

int main() {

	FIO;

	int n;

	cin>>n;

	vector<int> vec(n);

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

	memset(sum,0,sizeof(sum));

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

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

			for(int k=i;k<=j;k++) sum[i][j]+=vec[k];

		}

	}

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

	lli ans=fun(vec,0,n-1);

	cout<<ans<<endl;

}

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

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

#define PI 3.141592653589793238462643383279502884L

#define lli long long int

#define d double

#define mod 1000000007

#define mx 100001

using namespace std;

int main() {

	FIO;

	int n;

	cin>>n;

	vector<int> vec(n);

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

	lli sum[n][n];

	memset(sum,0,sizeof(sum));

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

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

			for(int k=i;k<=j;k++) sum[i][j]+=vec[k];

		}

	}

	lli inf=400000000001;

	lli dp[n][n];

	memset(dp,inf,sizeof(dp));

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

		dp[i][i]=0;

		if(i!=n-1) dp[i][i+1]=vec[i]+vec[i+1];

	}

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

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

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

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

			}

		}

	}

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

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

#include <ext/pb_ds/assoc_container.hpp>

#define F first

#define S second

#define PB push_back

#define REP(i,a,b) for (int i = a ; i <= b ; i++)

#define REPI(i,a,b) for (int i = a ; i >= b ; i--)

using namespace __gnu_pbds;

using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pi;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;



const ll OO = 1e18+7;

const int MOD = 1e9+7;

const int N = 4e2+7;



int n;

int a[N];

ll pref[N];

ll mem[N][N];



ll dp(int l,int r)

{

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

    if (ret != -1) return ret;

    if (l==r) return 0;

    ret = OO;

    REP(i,l,r-1)

    {

        ret = min(ret,dp(l,i)+dp(i+1,r)-pref[l-1]+pref[r]);

    }

    return ret;

}



int main()

{

    ios::sync_with_stdio(0);

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

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

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

    memset(mem,-1,sizeof mem);



    cin >> n;

    REP(i,1,n) {cin >> a[i];pref[i] = pref[i-1]+a[i];}

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

    return 0;

}


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

#include <ext/pb_ds/assoc_container.hpp>

#define F first

#define S second

#define PB push_back

#define REP(i,a,b) for (int i = a ; i <= b ; i++)

#define REPI(i,a,b) for (int i = a ; i >= b ; i--)

using namespace __gnu_pbds;

using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pi;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;



const ll OO = 1e18+7;

const int MOD = 1e9+7;

const int N = 4e2+7;



int n;

int a[N];

ll dp[N][N];

ll pref[N];



int main()

{

    ios::sync_with_stdio(0);

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

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

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





    cin >> n;

    REP(i,0,n-1) {cin >> a[i];}

     pref[0] = a[0];

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







    REP(len,1,n-1)

    {

        REP(l,0,n-1)

        {

            int r = l+len;

            if (r > n-1) break;

            dp[l][r] = OO;

            REP(i,l,r-1)

            {

                ll tmp = dp[l][i] + dp[i+1][r];

                if (l != 0) tmp += pref[r]-pref[l-1];

                else tmp += pref[r];

                dp[l][r] = min(dp[l][r],tmp);

            }

        }

    }

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

    return 0;

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

#define ll long long int

#define mp make_pair

#define pb push_back

#define ff first 

#define ss second

#define mod 1000000007

#define lim 100005

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

using namespace std;



int main()

{

	nfs_mw;

	int i,d,j,k,n,a[401]; ll dp[401][401] = {}, part[401] = {};

	cin>>n;

	for(i=1; i<=n; i++) { cin>>a[i]; part[i] = part[i-1] + a[i]; }

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

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

			j = i+d;

			dp[i][j] = 1e18;

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

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

		}

	cout<<dp[1][n];

}

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

#define ull uint64_t

#define ll long long int

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define mx5 100005

#define mx6 1000005

#define mod 1000000007

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

using namespace std;



ll dp[401][401] = {}, part[401] = {};



int main() {

    nfs

    int i, j, k, n, a, d;

    cin >> n;

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

        cin >> a;

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

        dp[i][i] = 0;

    }



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

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

            dp[i][j] = 1e18;

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

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

            }

            dp[i][j] += part[j] - part[i-1];

        }

    }

    cout << dp[1][n];

}