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

using namespace std;

typedef unsigned long long int ll;

const ll inf = 10000000010000000;

ll dp[410][410];

ll arr[410];

ll cumi[410];



ll go(ll i, ll j){

    if(i >= j)   return 0;

    ll &ret = dp[i][j];



    if(ret != -1)   return ret;

    ll ans = inf;

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

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

    }

    return ret = ans + cumi[j]-cumi[i-1];

}

int main(){

    memset(dp,-1,sizeof dp);

    ll n;

    scanf("%llu",&n);



    for(ll i = 1; i <= n; i++)  scanf("%llu",arr+i);

    for(ll i = 1; i <= n; i++)  cumi[i] = cumi[i-1] + arr[i];

    ll ans = go(1,n);

    printf("%llu\n",ans);

}


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

#include <unordered_map>

#include <unordered_set>

using namespace std;

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

//	Table is the complete reverse of dp

//	Always think of the pattern (LCM, GCD)

//	Be careful of unsigned

//	double epsilon = FLT_EPSILON;

//	Think of a solution that gets TLE and optimize it

int n;

ll **dp, *x;



int main()

{

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

    cin >> n;

    x = new ll[n];

    dp = new ll *[n];

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

    {

    	cin >> x[i];

    	dp[i] = new ll[n];

    	dp[i][i] = 0;

    	if(i)

    	{

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

    		dp[i - 1][i] = x[i] - (i - 1? x[i - 2]: 0);

    	}

    }

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

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

    	{

    		ll &ret = dp[i][i + sz];

    		ret = 1e16;

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

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

    		ret += x[i + sz] - (i? x[i - 1]: 0);

    	}

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

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<string>

#include<vector>

#include<random>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<algorithm>

#define endl "\n"

#define fi first

#define se second

#define db double

#define gcd __gcd

#define pb push_back

#define mp make_pair

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

#define PII  pair<int, int> 

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

#define debug(x) cout << #x << " = " << x << endl

#define rep(i, a, b) for(__typeof(b) i = a; i <= (b); i++)

#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)

#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }

template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }

typedef long long ll;

typedef unsigned long long ull;

const db eps = 1e-9;

const db PI = acos(-1);

const int inf = 0x3f3f3f3f;

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

const int maxn = (int)4e2 + 5;//remember to modify it, No RE or MLE

const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;



int a[maxn];

ll dp[maxn][maxn], sum[maxn];

int n;



int main()

{

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i), sum[i] = sum[i-1] + a[i];

	memset(dp, 0x3f, sizeof dp);

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

	rep(len, 2, n){

		rep(l, 1, n - len + 1){

			int r = l + len - 1;

			rep(mid, l, r - 1){

				dp[l][r] = qmin(dp[l][r], dp[l][mid] + dp[mid+1][r] + sum[r] - sum[l-1]);

			}

		}

	}

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

	return 0;

}

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

#include <unordered_map>

#include <unordered_set>

using namespace std;

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

//	Table is the complete reverse of dp

//	Always think of the pattern (LCM, GCD)

//	Be careful of unsigned

//	double epsilon = FLT_EPSILON;

//	Think of a solution that gets TLE and optimize it

int n;

ll **dp, *x;



int main()

{

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

    cin >> n;

    x = new ll[n];

    dp = new ll *[n];

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

    {

    	cin >> x[i];

    	dp[i] = new ll[n];

    	dp[i][i] = 0;

    	if(i)

    	{

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

    		dp[i - 1][i] = x[i] - (i - 1? x[i - 2]: 0);

    	}

    }

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

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

    	{

    		ll &ret = dp[i][i + sz];

    		ret = 1e16;

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

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

    		ret += x[i + sz] - (i? x[i - 1]: 0);

    	}

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

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

using namespace std;



int n;

long long arr[401];

long long dp[401][401];



long long getrange(int i, int  j){

	return (arr[j] - (i>0 ? arr[i-1]:0));

}



long long solve(int i, int j){

	if(i==j) return 0;

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



	dp[i][j] = 1e17;

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

		dp[i][j] = min(dp[i][j],

					solve(i, k) + solve(k+1, j)+

					getrange(i, k) + getrange(k+1, j));	

	}

	return dp[i][j];

}



int main(){

	scanf("%d", &n);

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

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

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

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

	}

	memset(dp, -1, sizeof dp);

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

	return 0;

}

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

#include <unordered_map>

#include <unordered_set>

using namespace std;

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

//	Table is the complete reverse of dp

//	Always think of the pattern (LCM, GCD)

//	Be careful of unsigned

//	double epsilon = FLT_EPSILON;

//	Think of a solution that gets TLE and optimize it

int n;

ll **dp, *x;



int main()

{

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

    cin >> n;

    x = new ll[n];

    dp = new ll *[n];

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

    {

    	cin >> x[i];

    	dp[i] = new ll[n];

    	dp[i][i] = 0;

    	if(i)

    	{

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

    		dp[i - 1][i] = x[i] - (i - 1? x[i - 2]: 0);

    	}

    }

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

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

    	{

    		ll &ret = dp[i][i + sz];

    		ret = 1e16;

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

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

    		ret += x[i + sz] - (i? x[i - 1]: 0);

    	}

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

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



using namespace std;



typedef long long ll;



const int N = 405;



ll dp[N][N];

int n;

ll pref[N];



ll go(int l, int r) {

  if(l >= r) return 0;

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

  ll cost = 1e18;

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

    cost = min(cost, go(l, i) + go(i + 1, r) + pref[r] - pref[l - 1]);

  }

  return dp[l][r] = cost;

}



int main() {

  cin >> n; memset(dp, -1, sizeof dp);

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

    ll x; cin >> x;

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

  }

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

}

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

using namespace std;

#define IO ios_base::sync_with_stdio(false)

#define ll long long

ll a[600000], vs[600000], dp[3000][3000], fs[500][500];

map<int,int>mp;

string s , s1;

ll f(ll l, ll r)

{

    ll i, j, n, mn=LLONG_MAX, k;

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

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

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

        k = f(l,i)+f(i+1,r);

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

        if(j<mn){

            mn = j ; fs[l][r] = k;

        }

    }

    dp[l][r]=mn; return fs[l][r];

}

int main()

{

    IO;

    ll j=0, n, m, k, m1, m2, a1=0, a2=0, l  = 1, t=3, mn, cnt=0, mx=0, h=0, mod=1e8+7, i; int tc=0;

    //cin>>t;

    //while(t--){

        cin>>n;



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

              cin>>a[i];



        j = f(1, n); cout<<dp[1][n]<<endl;



    //}

    return 0;

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

using namespace std;

typedef unsigned long long int ll;

const ll inf = 10000000010000000;

ll dp[410][410];

ll arr[410];

ll cumi[410];



ll go(ll i, ll j){

    if(i >= j)   return 0;

    ll &ret = dp[i][j];



    if(ret != -1)   return ret;

    ll ans = inf;

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

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

    }

    return ret = ans + cumi[j]-cumi[i-1];

}

int main(){

    memset(dp,-1,sizeof dp);

    ll n;

    scanf("%llu",&n);



    for(ll i = 1; i <= n; i++)  scanf("%llu",arr+i);

    for(ll i = 1; i <= n; i++)  cumi[i] = cumi[i-1] + arr[i];

    ll ans = go(1,n);

    printf("%llu\n",ans);

}


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

using namespace std;

#define IO ios_base::sync_with_stdio(false)

#define ll long long

ll a[600000], vs[600000], dp[3000][3000], fs[500][500];

map<int,int>mp;

string s , s1;

ll f(ll l, ll r)

{

    ll i, j, n, mn=LLONG_MAX, k;

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

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

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

        k = f(l,i)+f(i+1,r);

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

        if(j<mn){

            mn = j ; fs[l][r] = k;

        }

    }

    dp[l][r]=mn; return fs[l][r];

}

int main()

{

    IO;

    ll j=0, n, m, k, m1, m2, a1=0, a2=0, l  = 1, t=3, mn, cnt=0, mx=0, h=0, mod=1e8+7, i; int tc=0;

    //cin>>t;

    //while(t--){

        cin>>n;



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

              cin>>a[i];



        j = f(1, n); cout<<dp[1][n]<<endl;



    //}

    return 0;

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<string>

#include<vector>

#include<random>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<algorithm>

#define endl "\n"

#define fi first

#define se second

#define db double

#define gcd __gcd

#define pb push_back

#define mp make_pair

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

#define PII  pair<int, int> 

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

#define debug(x) cout << #x << " = " << x << endl

#define rep(i, a, b) for(__typeof(b) i = a; i <= (b); i++)

#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)

#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }

template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }

typedef long long ll;

typedef unsigned long long ull;

const db eps = 1e-9;

const db PI = acos(-1);

const int inf = 0x3f3f3f3f;

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

const int maxn = (int)4e2 + 5;//remember to modify it, No RE or MLE

const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;



int a[maxn];

ll dp[maxn][maxn], sum[maxn];

int n;



int main()

{

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i), sum[i] = sum[i-1] + a[i];

	memset(dp, 0x3f, sizeof dp);

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

	rep(len, 2, n){

		rep(l, 1, n - len + 1){

			int r = l + len - 1;

			rep(mid, l, r - 1){

				dp[l][r] = qmin(dp[l][r], dp[l][mid] + dp[mid+1][r] + sum[r] - sum[l-1]);

			}

		}

	}

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

	return 0;

}

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

using namespace std;

#define IO ios_base::sync_with_stdio(false)

#define ll long long

ll a[600000], vs[600000], dp[3000][3000], fs[500][500];

map<int,int>mp;

string s , s1;

ll f(ll l, ll r)

{

    ll i, j, n, mn=LLONG_MAX, k;

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

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

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

        k = f(l,i)+f(i+1,r);

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

        if(j<mn){

            mn = j ; fs[l][r] = k;

        }

    }

    dp[l][r]=mn; return fs[l][r];

}

int main()

{

    IO;

    ll j=0, n, m, k, m1, m2, a1=0, a2=0, l  = 1, t=3, mn, cnt=0, mx=0, h=0, mod=1e8+7, i; int tc=0;

    //cin>>t;

    //while(t--){

        cin>>n;



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

              cin>>a[i];



        j = f(1, n); cout<<dp[1][n]<<endl;



    //}

    return 0;

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

using namespace std;



int n;

long long arr[401];

long long dp[401][401];



long long getrange(int i, int  j){

	return (arr[j] - (i>0 ? arr[i-1]:0));

}



long long solve(int i, int j){

	if(i==j) return 0;

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



	dp[i][j] = 1e17;

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

		dp[i][j] = min(dp[i][j],

					solve(i, k) + solve(k+1, j)+

					getrange(i, k) + getrange(k+1, j));	

	}

	return dp[i][j];

}



int main(){

	scanf("%d", &n);

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

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

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

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

	}

	memset(dp, -1, sizeof dp);

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

	return 0;

}

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

using namespace std;

#define IO ios_base::sync_with_stdio(false)

#define ll long long

ll a[600000], vs[600000], dp[3000][3000], fs[500][500];

map<int,int>mp;

string s , s1;

ll f(ll l, ll r)

{

    ll i, j, n, mn=LLONG_MAX, k;

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

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

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

        k = f(l,i)+f(i+1,r);

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

        if(j<mn){

            mn = j ; fs[l][r] = k;

        }

    }

    dp[l][r]=mn; return fs[l][r];

}

int main()

{

    IO;

    ll j=0, n, m, k, m1, m2, a1=0, a2=0, l  = 1, t=3, mn, cnt=0, mx=0, h=0, mod=1e8+7, i; int tc=0;

    //cin>>t;

    //while(t--){

        cin>>n;



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

              cin>>a[i];



        j = f(1, n); cout<<dp[1][n]<<endl;



    //}

    return 0;

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



using namespace std;



typedef long long ll;



const int N = 405;



ll dp[N][N];

int n;

ll pref[N];



ll go(int l, int r) {

  if(l >= r) return 0;

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

  ll cost = 1e18;

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

    cost = min(cost, go(l, i) + go(i + 1, r) + pref[r] - pref[l - 1]);

  }

  return dp[l][r] = cost;

}



int main() {

  cin >> n; memset(dp, -1, sizeof dp);

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

    ll x; cin >> x;

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

  }

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

}

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

using namespace std;

#define vb __int128

#define ll long long

#define ld long double

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

#define stoink stack<ll>

#define vec vector <ll>

#define vg vector<vector<ll> >

#define vgw vector<vector<pair<ll,ll> >

#define pa pair<ll,ll>

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

#define prec 0.00000000000000000001

#define inf (ll)1e18

#define mod 998244353

ll dp[401][401];

vec arr;

vec pre;

ll n;

ll func(ll l,ll r) {

	if(l == r)

		return 0;

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

		return dp[l][r];

	ll res = inf,i;

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

		res = min(res,func(l,i) + func(i+1,r) + pre[r] - pre[l-1]);

	}

	return dp[l][r] = res;

}

int main()

{	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cin >> n;

	arr.resize(n+1);

	pre.resize(n+1,0);

	ll i;

	ll counti = n;

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

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

			dp[i][j] = -1;

	ll cost = 0;

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

		cin >> arr[i];

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

	}

	cout << func(1,n);

	return 0;

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

using namespace std;

typedef unsigned long long int ll;

const ll inf = 10000000010000000;

ll dp[410][410];

ll arr[410];

ll cumi[410];



ll go(ll i, ll j){

    if(i >= j)   return 0;

    ll &ret = dp[i][j];



    if(ret != -1)   return ret;

    ll ans = inf;

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

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

    }

    return ret = ans + cumi[j]-cumi[i-1];

}

int main(){

    memset(dp,-1,sizeof dp);

    ll n;

    scanf("%llu",&n);



    for(ll i = 1; i <= n; i++)  scanf("%llu",arr+i);

    for(ll i = 1; i <= n; i++)  cumi[i] = cumi[i-1] + arr[i];

    ll ans = go(1,n);

    printf("%llu\n",ans);

}


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

using namespace std;

#define vb __int128

#define ll long long

#define ld long double

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

#define stoink stack<ll>

#define vec vector <ll>

#define vg vector<vector<ll> >

#define vgw vector<vector<pair<ll,ll> >

#define pa pair<ll,ll>

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

#define prec 0.00000000000000000001

#define inf (ll)1e18

#define mod 998244353

ll dp[401][401];

vec arr;

vec pre;

ll n;

ll func(ll l,ll r) {

	if(l == r)

		return 0;

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

		return dp[l][r];

	ll res = inf,i;

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

		res = min(res,func(l,i) + func(i+1,r) + pre[r] - pre[l-1]);

	}

	return dp[l][r] = res;

}

int main()

{	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cin >> n;

	arr.resize(n+1);

	pre.resize(n+1,0);

	ll i;

	ll counti = n;

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

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

			dp[i][j] = -1;

	ll cost = 0;

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

		cin >> arr[i];

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

	}

	cout << func(1,n);

	return 0;

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<string>

#include<vector>

#include<random>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<algorithm>

#define endl "\n"

#define fi first

#define se second

#define db double

#define gcd __gcd

#define pb push_back

#define mp make_pair

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

#define PII  pair<int, int> 

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

#define debug(x) cout << #x << " = " << x << endl

#define rep(i, a, b) for(__typeof(b) i = a; i <= (b); i++)

#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)

#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }

template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }

typedef long long ll;

typedef unsigned long long ull;

const db eps = 1e-9;

const db PI = acos(-1);

const int inf = 0x3f3f3f3f;

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

const int maxn = (int)4e2 + 5;//remember to modify it, No RE or MLE

const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;



int a[maxn];

ll dp[maxn][maxn], sum[maxn];

int n;



int main()

{

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i), sum[i] = sum[i-1] + a[i];

	memset(dp, 0x3f, sizeof dp);

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

	rep(len, 2, n){

		rep(l, 1, n - len + 1){

			int r = l + len - 1;

			rep(mid, l, r - 1){

				dp[l][r] = qmin(dp[l][r], dp[l][mid] + dp[mid+1][r] + sum[r] - sum[l-1]);

			}

		}

	}

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

	return 0;

}

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

using namespace std;

#define vb __int128

#define ll long long

#define ld long double

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

#define stoink stack<ll>

#define vec vector <ll>

#define vg vector<vector<ll> >

#define vgw vector<vector<pair<ll,ll> >

#define pa pair<ll,ll>

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

#define prec 0.00000000000000000001

#define inf (ll)1e18

#define mod 998244353

ll dp[401][401];

vec arr;

vec pre;

ll n;

ll func(ll l,ll r) {

	if(l == r)

		return 0;

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

		return dp[l][r];

	ll res = inf,i;

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

		res = min(res,func(l,i) + func(i+1,r) + pre[r] - pre[l-1]);

	}

	return dp[l][r] = res;

}

int main()

{	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cin >> n;

	arr.resize(n+1);

	pre.resize(n+1,0);

	ll i;

	ll counti = n;

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

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

			dp[i][j] = -1;

	ll cost = 0;

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

		cin >> arr[i];

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

	}

	cout << func(1,n);

	return 0;

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

using namespace std;



int n;

long long arr[401];

long long dp[401][401];



long long getrange(int i, int  j){

	return (arr[j] - (i>0 ? arr[i-1]:0));

}



long long solve(int i, int j){

	if(i==j) return 0;

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



	dp[i][j] = 1e17;

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

		dp[i][j] = min(dp[i][j],

					solve(i, k) + solve(k+1, j)+

					getrange(i, k) + getrange(k+1, j));	

	}

	return dp[i][j];

}



int main(){

	scanf("%d", &n);

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

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

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

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

	}

	memset(dp, -1, sizeof dp);

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

	return 0;

}

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

using namespace std;

#define vb __int128

#define ll long long

#define ld long double

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

#define stoink stack<ll>

#define vec vector <ll>

#define vg vector<vector<ll> >

#define vgw vector<vector<pair<ll,ll> >

#define pa pair<ll,ll>

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

#define prec 0.00000000000000000001

#define inf (ll)1e18

#define mod 998244353

ll dp[401][401];

vec arr;

vec pre;

ll n;

ll func(ll l,ll r) {

	if(l == r)

		return 0;

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

		return dp[l][r];

	ll res = inf,i;

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

		res = min(res,func(l,i) + func(i+1,r) + pre[r] - pre[l-1]);

	}

	return dp[l][r] = res;

}

int main()

{	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	cin >> n;

	arr.resize(n+1);

	pre.resize(n+1,0);

	ll i;

	ll counti = n;

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

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

			dp[i][j] = -1;

	ll cost = 0;

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

		cin >> arr[i];

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

	}

	cout << func(1,n);

	return 0;

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



using namespace std;



typedef long long ll;



const int N = 405;



ll dp[N][N];

int n;

ll pref[N];



ll go(int l, int r) {

  if(l >= r) return 0;

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

  ll cost = 1e18;

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

    cost = min(cost, go(l, i) + go(i + 1, r) + pref[r] - pref[l - 1]);

  }

  return dp[l][r] = cost;

}



int main() {

  cin >> n; memset(dp, -1, sizeof dp);

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

    ll x; cin >> x;

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

  }

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

}

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

using namespace std;

using ll = long long;

using PII = pair<int, int>;

using VI = vector<int>;



const int N = 405;

int a[N];

ll pre[N], best[N][N];



int main() {

#ifdef LOCAL_EXEC

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

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

#else

  ios_base::sync_with_stdio(false); cin.tie(NULL);

#endif



  int n; cin >> n;



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

    cin >> a[i];

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

  }



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

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

      int r = l + len - 1;

      best[l][r] = 1e18;

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

        best[l][r] = min(best[l][r], best[l][m] + best[m + 1][r]);

      }

      best[l][r] += pre[r] - pre[l - 1];

    }

  }



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



  return 0;

}