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.310692384152889x):
#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;

}
// 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.283187051439973x):
#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;

}
// 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.250626904753402x):
#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;

}
// 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.3151329232209013x):
#include<cstdio>

#include<math.h>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define Case int t;scanf("%d", &t);while(t--)

typedef long long ll;

const int Max = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

int n;

ll a[405];

ll dp[405][405];

ll ans[405][405];



int main(){

	cin >> n;

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

		cin >> a[i];

		dp[i][i] = a[i];

	}



	

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

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

			int j = i+l;

			if(ans[i][j-1]+dp[i][j-1]+a[j] < ans[i+1][j]+dp[i+1][j]+a[i]){

				ans[i][j] = ans[i][j-1]+dp[i][j-1]+a[j];

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

			}

			else{

				ans[i][j] = ans[i+1][j]+dp[i+1][j]+a[i];

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

			}

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

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

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

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

				}

			}

		}

	}



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

}
// 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.3338301494294997x):
#include<cstdio>

#include<math.h>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define Case int t;scanf("%d", &t);while(t--)

typedef long long ll;

const int Max = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

int n;

ll a[405];

ll dp[405][405];

ll ans[405][405];



int main(){

	cin >> n;

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

		cin >> a[i];

		dp[i][i] = a[i];

	}



	

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

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

			int j = i+l;

			if(ans[i][j-1]+dp[i][j-1]+a[j] < ans[i+1][j]+dp[i+1][j]+a[i]){

				ans[i][j] = ans[i][j-1]+dp[i][j-1]+a[j];

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

			}

			else{

				ans[i][j] = ans[i+1][j]+dp[i+1][j]+a[i];

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

			}

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

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

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

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

				}

			}

		}

	}



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

}
// 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.3060493962683535x):
#include<cstdio>

#include<math.h>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define Case int t;scanf("%d", &t);while(t--)

typedef long long ll;

const int Max = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

int n;

ll a[405];

ll dp[405][405];

ll ans[405][405];



int main(){

	cin >> n;

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

		cin >> a[i];

		dp[i][i] = a[i];

	}



	

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

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

			int j = i+l;

			if(ans[i][j-1]+dp[i][j-1]+a[j] < ans[i+1][j]+dp[i+1][j]+a[i]){

				ans[i][j] = ans[i][j-1]+dp[i][j-1]+a[j];

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

			}

			else{

				ans[i][j] = ans[i+1][j]+dp[i+1][j]+a[i];

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

			}

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

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

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

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

				}

			}

		}

	}



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

}
// 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.273163213525848x):
#include<cstdio>

#include<math.h>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define Case int t;scanf("%d", &t);while(t--)

typedef long long ll;

const int Max = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

int n;

ll a[405];

ll dp[405][405];

ll ans[405][405];



int main(){

	cin >> n;

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

		cin >> a[i];

		dp[i][i] = a[i];

	}



	

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

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

			int j = i+l;

			if(ans[i][j-1]+dp[i][j-1]+a[j] < ans[i+1][j]+dp[i+1][j]+a[i]){

				ans[i][j] = ans[i][j-1]+dp[i][j-1]+a[j];

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

			}

			else{

				ans[i][j] = ans[i+1][j]+dp[i+1][j]+a[i];

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

			}

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

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

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

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

				}

			}

		}

	}



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

}
// 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.3215035706468887x):
#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <queue>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

const long long INF = 1e18;



ll n;

ll a[405], dp[405][405], pre[405];





int main(){

	cin >> n;

	pre[0] = 0;

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

		cin >> a[i];

		dp[i][i] = 0;

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

	}

	ll ans = 0, tmp = 0;

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

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

			ll r = l + i - 1;

			dp[l][r] = INF;

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

				dp[l][r] = dp[l][r] <  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1] ? dp[l][r] :  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1];

			}

		}

	}

	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.3402522467894524x):
#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <queue>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

const long long INF = 1e18;



ll n;

ll a[405], dp[405][405], pre[405];





int main(){

	cin >> n;

	pre[0] = 0;

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

		cin >> a[i];

		dp[i][i] = 0;

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

	}

	ll ans = 0, tmp = 0;

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

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

			ll r = l + i - 1;

			dp[l][r] = INF;

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

				dp[l][r] = dp[l][r] <  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1] ? dp[l][r] :  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1];

			}

		}

	}

	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.3123950481759334x):
#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <queue>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

const long long INF = 1e18;



ll n;

ll a[405], dp[405][405], pre[405];





int main(){

	cin >> n;

	pre[0] = 0;

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

		cin >> a[i];

		dp[i][i] = 0;

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

	}

	ll ans = 0, tmp = 0;

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

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

			ll r = l + i - 1;

			dp[l][r] = INF;

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

				dp[l][r] = dp[l][r] <  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1] ? dp[l][r] :  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1];

			}

		}

	}

	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.279418371158418x):
#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <queue>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

const long long INF = 1e18;



ll n;

ll a[405], dp[405][405], pre[405];





int main(){

	cin >> n;

	pre[0] = 0;

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

		cin >> a[i];

		dp[i][i] = 0;

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

	}

	ll ans = 0, tmp = 0;

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

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

			ll r = l + i - 1;

			dp[l][r] = INF;

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

				dp[l][r] = dp[l][r] <  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1] ? dp[l][r] :  dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1];

			}

		}

	}

	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.2610659611570507x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;



int main(){



    cin.tie( nullptr );

    ios_base::sync_with_stdio(0);



    int n; cin >> n;



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

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

        cin >> v[i], v[i]+=v[i-1];



    vector< vector<ll> > dp;

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



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

    for(int i=1, j=2; j<=n; i++, j++) dp[i][j] = v[j] - v[i-1];



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

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

        ll tot = v[j] - v[i-1];

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

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

    }

    cout << dp[1][n] << "\n";



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

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

//        cout << dp[i][j] << " \n"[j==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.2793265376122034x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;



int main(){



    cin.tie( nullptr );

    ios_base::sync_with_stdio(0);



    int n; cin >> n;



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

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

        cin >> v[i], v[i]+=v[i-1];



    vector< vector<ll> > dp;

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



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

    for(int i=1, j=2; j<=n; i++, j++) dp[i][j] = v[j] - v[i-1];



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

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

        ll tot = v[j] - v[i-1];

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

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

    }

    cout << dp[1][n] << "\n";



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

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

//        cout << dp[i][j] << " \n"[j==n];



    return 0;

}