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

using namespace std;

typedef long long ll;

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

ll run();



int main() {

#ifdef home

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

    freopen("d", "w", stderr);

#endif

    cout.precision(15);

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    run();

    return 0;

}

const ll inf = (1e9+5);

void max_self(ll &a, ll b) {

    a = max(a, b);

}

void min_self(ll &a, ll b) {

    a = min(a, b);

}

void mul(ll &a, ll b) {

    a = (a * b) % mod;

}

void add_self(ll &a, ll b){

    a+=b;

    if(a>=mod)

        a-=mod;

}

ll gcd(ll a, ll b){

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

}



vector<ll> a(405);

vector<ll> ps(405);

ll dp[405][405];



ll solve(int i, int j){

    if(i==j)

        return 0;

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

        return dp[i][j];

    ll s = ps[j]-ps[i-1];

    ll ans = LLONG_MAX;

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

        ans = min(ans,solve(i,k)+solve(k+1,j)+s);

    }

    return dp[i][j] = ans;

}



ll run() {

    int n;

    cin>>n;

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

    ll s = 0;

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

        cin >> a[i];

        s+=a[i];

        ps[i] = s;

    }



    ll ans = solve(1,n);

    cout<<ans;

    return 0;

}




























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

using namespace std;

typedef long long ll;

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

const int nax = 405;

const ll INF = 1e18+5;

ll dp[405][405];



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

	

	int n;

	cin>>n;

	vector<ll> a(n);

	for(ll &x : a){

		cin>>x;

	}

	vector<ll> p(n);

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

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

	}

	auto sum = [&](int i,int j){

		if(i>0)

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

		else return p[j];	

	};

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

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

			if(l==r){

				dp[l][r] = 0;

			}

			else{

				dp[l][r] = INF;

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

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

				}

			}

		}

	}

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

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <iomanip>

#include <algorithm>

#include <tuple>

#include <vector>

using namespace std;



int N;

long long dp[404][404];

long long a[404];



long long solve(int s, int t){

    if(dp[s][t] != -1) return dp[s][t];

    if(t==s+1) return 0;

    long long sm = 0;

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

        sm += a[i];

    long long mn = 1LL<<60;

    for(int k=s+1; k<t; k++){

        mn = min(mn, solve(s, k) + solve(k, t));

    }

    dp[s][t] = mn + sm;

    return dp[s][t];

}



int main(){

    cin >> N;

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

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

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

            dp[i][j] = -1;



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

    return 0;

}

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

using namespace std;

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

#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }

template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }



int main(){

    int N;

    cin >> N;

    vector<int> a(N);

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



    vector<vector<long long>> dp(N, vector<long long>(N, 1LL<<60));

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

        dp[i][i] = 0;



    vector<long long> b(N+1);

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

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



    for(int k=2; k<=N; k++){

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

            int right = left+k-1;

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

                dp[left][right] = min(dp[left][right], dp[left][mid] + dp[mid+1][right] + b[right+1]-b[left]);

            }

        }

    }

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<queue>

#include<stack>

using namespace std;

#define MOD 1000000007

#define INF (1LL<<60)

#define EPS (1e-10)

typedef long long Int;

typedef pair<Int, Int> P;



#define max(x, y) ((x)>(y)?(x):(y))

#define min(x, y) ((x)<(y)?(x):(y))



Int a[432];

Int sum[432];

Int dp[432][432];

Int n;

int main(){

  cin >> n;

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

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

      dp[i][j] = INF;

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

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

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

      int j = i + dif;

      if(dif == 1){

	dp[i][j] = 0;

      }

      else{

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

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

	}

      }

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

    }

  }

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

  return 0;

}

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

#include<cstdio>

#include<algorithm>

#include<cassert>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<queue>

#include<stack>

using namespace std;

#define MOD 1000000007

#define MOD2 998244353

#define INF ((1<<30)-1)

#define LINF (1LL<<60)

#define EPS (1e-10)

typedef long long Int;

typedef pair<Int, Int> P;



Int sum[440][440];

Int dp[440][440];

Int a[440];

Int n;

int main(){

    cin >> n;

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

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

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

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

            sum[l][r] = sum[l][r-1] + a[r-1];

        }

    }



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

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

            int r = l + width;

            dp[l][r] = LINF;

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

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

            }

        }

    }

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

    return 0;

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

using namespace std;



#define int long long

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

#define print(a,n)  for(int i = 0;i < n;i++)cout <<a[i] <<' ';cout<<endl;

#define endl  '\n'

#define vi  vector<int>

#define inf 1e17

// Tushar Goyal : Chalie Shuru karte hai

#define db(...) 		__f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << '\n'; }

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args) {

	const char* comma = strchr(names + 1, ',');

	cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);

}





int dp[401][401];

int sum[401][401];

// sum[i][j] denotes the sum from index =i to index = j in vector a;

vi a(401);



int cost(int i, int j)

{

	if (i == j )return 0;

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



	int mincost = inf;

	// transition time is O(n)

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

	{

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

	}



	return dp[i][j] = mincost;

}



void preprocess(vi a, int n)

{



	// O(n^2)

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

	{

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

		{

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

			if (i != j)sum[i][j] += sum[i][j - 1];

		}

	}



}



void solve()

{

	int n; cin >> n;

	scan(a, n);

	// print(a, n);



	memset(dp, -1, sizeof dp);

	memset(sum, 0, sizeof sum);

	preprocess(a, n);



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

		{

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

			{

				db(i, j, sum[i][j]);

			}

		}

	*/



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



}



int32_t main()

{

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

	solve();

	return 0;

}

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

using namespace std;



#define int long long

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

#define print(a,n)  for(int i = 0;i < n;i++)cout <<a[i] <<' ';cout<<endl;

#define endl  '\n'

#define vi  vector<int>

#define inf 1e17

// Tushar Goyal : Chalie Shuru karte hai



int dp[401][401];

int sum[401];

// sum[i][j] denotes the sum from index =i to index = j in vector a;

vi a(401);





void preprocess(int n)

{

	sum[0] = a[0];

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

	{

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

	}

}



void solve()

{

	int n; cin >> n;

	scan(a, n);

	// print(a, n);



	memset(sum, 0, sizeof sum);

	preprocess(n);



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

	{

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

		{

			if (L == R)dp[L][R] = 0;

			else

			{

				dp[L][R] = inf;

				int s = sum[R];

				if (L - 1 >= 0)s -= sum[L - 1];

				for (int i = L ; i < R ; i++)

				{

					dp[L][R] = min(dp[L][R] , s + dp[L][i] + dp[i + 1][R] );

				}

			}

		}

	}



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

}



int32_t main()

{

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

	solve();

	return 0;

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

using namespace std;

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

#define ll long long



vector<int>a(401);

vector<vector<pair<ll,ll>>> dp(401,vector<pair<ll,ll>> (401,make_pair(-1,-1)));

pair<ll,ll> f(int i,int j)

{

  if(i==j) return make_pair(a[i],0);

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

  pair<ll,ll> ans={0,1e14},l,r;

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

  {

    l = f(i,k);

    r = f(k+1,j);

    if(l.second+r.second + l.first +r.first < ans.second)

    {

      ans.first = l.first+r.first;

      ans.second = l.second+r.second + l.first +r.first;  

    }

  }  

  dp[i][j] = ans;

  return ans;

}



int main()

{

  int n;

  cin>>n;

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

  cout<<f(0,n-1).second;

  /*

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

  {

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

    {

      cout<<i<<" "<<j<<" "<<f(i,j)<<endl;

    }

  }

  */

  return 0;

}

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

using namespace std;

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

#define ll long long



int main()

{

   int n;

  cin>>n;

  int a[n+1];

  ll prefix[n+1];

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

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

  {

    cin>>a[i];

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

  }

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

  ll small;

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

  {

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

    {

      dp[i][j] = prefix[j]-prefix[i-1];

      small = 1e14;

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

      {

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

      }

      if(small != 1e14)

        dp[i][j] = dp[i][j] + small;

    }

  }

  cout<<dp[1][n];

  return 0;

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

using namespace std;

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

#define ll long long



vector<int>a(401);

vector<vector<pair<ll,ll>>> dp(401,vector<pair<ll,ll>> (401,make_pair(-1,-1)));

pair<ll,ll> f(int i,int j)

{

  if(i==j) return make_pair(a[i],0);

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

  pair<ll,ll> ans={0,1e14},l,r;

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

  {

    l = f(i,k);

    r = f(k+1,j);

    if(l.second+r.second + l.first +r.first < ans.second)

    {

      ans.first = l.first+r.first;

      ans.second = l.second+r.second + l.first +r.first;  

    }

  }  

  dp[i][j] = ans;

  return ans;

}



int main()

{

  int n;

  cin>>n;

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

  cout<<f(0,n-1).second;

  /*

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

  {

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

    {

      cout<<i<<" "<<j<<" "<<f(i,j)<<endl;

    }

  }

  */

  return 0;

}

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

using namespace std;

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

#define ll long long



int main()

{

  int n;

  cin>>n;

  int a[n+1];

  int r[n+1][n+1];

  for(int i =0;i<=n;i++){ for(int j=0;j<=n;j++) r[i][j]=0; }; 

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

  ll prefix[n+1];

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

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

  {

    cin>>a[i];

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

  }

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

  ll small;

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

  {

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

    {

      int j= i+d;

      if(i==j)

      {

        r[i][j] = i;

        dp[i][j] = 0; 

      }

      else

      {

        dp[i][j] = 1e14;

        for(int k=r[i][j-1];k<=min(r[i+1][j],n-1);k++)

        {

          if(dp[i][j]>dp[i][k] + dp[k+1][j])

          {

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

            r[i][i+d] = k;

          }

        }

        dp[i][i+d] += prefix[i+d]-prefix[i-1];

      }

    }

  }

  cout<<dp[1][n];

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <cstring>

#include <vector>

#include <algorithm>

#include <set>

#include <stack>

#include <deque>

#include <cmath>

#include <map>

using namespace std;

using ll = long long;

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}



ll n;

ll s[410] = {};

ll dp[410][410];



ll rec(ll l, ll r) {

    if (l == r) return 0;

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

    ll res = 1LL << 60;

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

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

    }

    return dp[l][r] = res;

}



int main() {

    cin >> n;

    rep(i, n) {

        ll tmp;

        cin >> tmp;

        s[i+1] = s[i] + tmp;

    }

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

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

}

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

using namespace std;

using ll = long long;

using vll = vector<ll>;

using vvll = vector<vll>;

using vc = vector<char>;

using vvc = vector<vc>;

using pll = pair<ll, ll>;

using stkll = vector<pll>;

const ll INF = 1LL << 60;

const ll MOD = 1e9 + 7;

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

#ifndef ONLINE_JUDGE

    #define debug(x) cerr << #x << ": " << x << endl;

#else

    #define debug(x)

#endif



ll dp[410][410];

ll a[410], sa[410];



int main() {

    cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);



    ll N; cin >> N;

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

    rep(i, N) sa[i+1] = sa[i] + a[i];



    for(ll w = 2; w <= N; w++) {

        for(ll l = 0; l + w <= N; l++) {

            ll r = l + w;

            dp[l][r] = INF;

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

                ll tmp = dp[l][m] + dp[m][r] + sa[r] - sa[l];

                chmin(dp[l][r], tmp);

            }

        }

    }

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

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

using namespace std;

#define int long long



signed main(){

  cin.tie(0);

  ios::sync_with_stdio(false);



  int n; cin >> n;

  vector<int> a(n),b(n+1,0);

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

    cin >> a[i];

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

  }



  vector< vector<int> > dp(401,vector<int>(401,-1));

  //dp[l][r] = {[l,r)を合体するときの最小コスト}



  function< int(int,int) > rec =

  [&](int l,int r){

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

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



    int cost = b[r] - b[l];

    int res = 1LL << 60;

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

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

    }

    return dp[l][r] = res;

  };

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



  return 0;

}


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

using namespace std;

#ifdef LOCAL_DEBUG

  #include "LOCAL_DEBUG.hpp"

#endif

#define int long long



signed main(){



  int n; cin >> n;

  vector<int> a(n);

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

    cin >> a[i];

  }



  vector<int> b(n+1);

  b[0] = 0;

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

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

  }



  static int dp[500][500];

  function< int(int,int) > rec =

  [&](int l,int r){

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

    if(dp[l][r] > 0) return dp[l][r];

    int res = 1LL << 60;

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

      res = min(res,rec(l,i) + rec(i,r) + (b[r] - b[l]));

    }

    return dp[l][r] = res;

  };

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



  return 0;

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

 

#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

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

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

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

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

#define pb push_back

#define ppb pop_back

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb;  

typedef long long ll;  

typedef double db;                      

 

 

const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;

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

const pii base = {1171, 3307}, Mod = {1e9 + 7, 1e9 + 9};

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, a[N], dp[N][N];



int get (int l, int r) {

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

}



int rec (int l, int r) {

	if (r == l)	

		return 0;

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

		return dp[l][r];



	dp[l][r] = INF;



	forn (L, l, r - 1) 

		dp[l][r] = min(dp[l][r], rec(l, L) + rec(L + 1, r) + get(l, L) + get(L + 1, r));		



	return dp[l][r];	

}





main () {

	cin >> n;

	forn (i, 1, n) {

		cin >> a[i]; 

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

	}



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

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

}



    

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

#include<iostream>

using namespace std;

const int MAXN = 410;

const long long INF = 0x7f7f7f7f7f7f7f; 

int n, a[MAXN];

long long sum[MAXN], f[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

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

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

			f[i][j] = INF;

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

		scanf("%d",&a[i]),sum[i] = sum[i-1]+a[i], f[i][i]=0;

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

		for(int i=1,j=i+l;i<=n&&j<=n;i++,j=i+l)

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

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

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

	return 0;

}
// Slower C++ solution:
//#pragma GCC target ("avx2,sse2")

//#pragma GCC optimization ("Ofast")

//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree <pair <ll, int>, null_type, less <pair <ll, int> >, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long

#define ull unsigned long long

#define db double

#define pb push_back

#define pf push_front

#define ppb pop_back

#define ppf pop_front

#define fi first

#define se second

#define mp make_pair

#define up_b upper_bound

#define low_b lower_bound

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

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

#define endl "\n"



#define left fsdsdfoisf

#define sum dpsdfioppsf

#define assign xcvjlkdjfio

#define trie fksdfkjkfnjuiv

#define next sidlfjsfkl

#define merge sdfksdkfsldf



#define int long long



using namespace std;



void dout() {

    cerr << endl;

}

template <typename Head, typename... Tail>

void dout(Head H, Tail... T) {

    cerr << H << ' ';

    dout(T...);

}



//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair <int, int> pii;



const int N = 407, inf = 1e15;

int n, a[N], p[N], dp[N][N];



int calc(int l, int r) {

    if (l >= r) {

        return 0;

    }

    int & res = dp[l][r];

    if (res != -1) {

        return res;

    }

    res = inf;

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

        res = min(res, calc(l, i) + calc(i + 1, r) + (p[i] - p[l - 1]) + (p[r] - p[i]));

    }

    return res;

}



void solve(int tc) {

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

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

    cin >> n;

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

        cin >> a[i];

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

    }

    cout << calc(1, n);

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

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

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

    int tc = 1;

//    cin >> tc;

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

        solve(i);

//        cleanup();

    }

}


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

#include<iostream>

using namespace std;

const int MAXN = 410;

const long long INF = 0x7f7f7f7f7f7f7f; 

int n, a[MAXN];

long long sum[MAXN], f[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

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

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

			f[i][j] = INF;

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

		scanf("%d",&a[i]),sum[i] = sum[i-1]+a[i], f[i][i]=0;

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

		for(int i=1,j=i+l;i<=n&&j<=n;i++,j=i+l)

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

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

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

	return 0;

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

 

#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

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

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

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

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

#define pb push_back

#define ppb pop_back

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb;  

typedef long long ll;  

typedef double db;                      

 

 

const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;

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

const pii base = {1171, 3307}, Mod = {1e9 + 7, 1e9 + 9};

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, a[N], dp[N][N];



int get (int l, int r) {

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

}



int rec (int l, int r) {

	if (r == l)	

		return 0;

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

		return dp[l][r];



	dp[l][r] = INF;



	forn (L, l, r - 1) 

		dp[l][r] = min(dp[l][r], rec(l, L) + rec(L + 1, r) + get(l, L) + get(L + 1, r));		



	return dp[l][r];	

}





main () {

	cin >> n;

	forn (i, 1, n) {

		cin >> a[i]; 

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

	}



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

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

}



    

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

using namespace std;

const int N = 405;

int n, a[N];

long long sum[N], mem[N][N];

bool vis[N][N];



long long dp(int i, int j) {

	if (i == j) {

		return 0;

	}

	if (vis[i][j]) {

		return mem[i][j];

	}

	vis[i][j] = true;



	long long ans = LLONG_MAX;

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

		ans = min(ans, dp(i, m) + dp(m + 1, j));

	}



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

	return mem[i][j] = cost + ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dp(1, n) << '\n';



	return 0;

}