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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


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

using namespace std;



#define ll long long

#define pb push_back

#define mp make_pair

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

#define f first

#define se second

#define lb lower_bound

#define ub upper_bound

#define pii pair<int, int>

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



const int N = 401, mod = 110119, inf = 1e9 + 7, LOG = 20;

ll n, a[N], dp[N][N], pr[N];



ll bp(int x, int y){

    if(y == 0)

        return 1;

    if(y % 2 == 0){

        ll z = bp(x, y / 2);

        return (z * z) % mod;

    }

    return (bp(x, y - 1) * x) % mod;

}



ll go(int l, int r){

    if(l == r)

        return 0;

    if(dp[l][r])

        return dp[l][r];

    ll ans = 1e18;

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

        ans = min(ans, go(l, i) + go(i + 1, r) + pr[r] - pr[l - 1]);

    dp[l][r] = ans;

    return ans;

}



int main(){

    boost;

    cin >> n;

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

        cin >> a[i];

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

    }

    cout << go(1, n);

    return 0;

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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


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

#define mn(a, b) (a < b ? a : b)

#define mx(a, b) (a > b ? a : b)

#define f first

#define s second

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

#define base 331



using namespace std;



typedef long long ll;

typedef unsigned long long ull;



int const MAXn = 4e2 + 2;



ll dp[MAXn][MAXn];

ll arr[MAXn];



int main(){



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

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int n;

    cin>>n;

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

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

            dp[i][j] = 1e17;

    }

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

        cin>>arr[i];

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

    }

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

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

            int j = i + d - 1;

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

                dp[i][j] = mn(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[j] - arr[i - 1]);

            }

        }

    }

    cout<<dp[1][n];

    return 0;

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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


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

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

#define line cout<<"----------------------"<<endl

#define mp make_pair

#define mod 1000000007

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

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll  mx=2000009;

ll ara[mx];

ll dp[409][409];

ll sum[409];

int main()

{

    ll n;

    cin>>n;

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

    {

        cin>>ara[i];

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

    }

    for(ll i=n;i>0;i--)

    {

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

        {

            dp[i][j]=LLONG_MAX;

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

            {

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

            }

        }

    }

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



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

using namespace std;

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

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 4e2 + 9, M = 1e5 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



ll mem[N][N], arr[N], pre[N];



ll solve(int start, int end) {

  if(start >= end)

    return 0;

  ll& ret =mem[start][end];

  if(~ret)

    return ret;

  ret = inf;

  for (int i = start; i < end; ++i) {

    ll c1 = solve(start, i);

    ll c2 = solve(i+1, end);

    ll sumL = pre[i] - pre[start - 1], sumR = pre[end] - pre[i];

    ret = min(ret, c1 + c2 + sumL + sumR);

  }

  return ret;

}



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  memset(mem, -1, sizeof mem);

  int n;

  cin >> n;

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

    cin >> arr[i], pre[i] += pre[i-1] + arr[i];

  cout << solve(1, n);

  return 0;

}


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

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

#define line cout<<"----------------------"<<endl

#define mp make_pair

#define mod 1000000007

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

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll  mx=2000009;

ll ara[mx];

ll dp[409][409];

ll sum[409];

int main()

{

    ll n;

    cin>>n;

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

    {

        cin>>ara[i];

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

    }

    for(ll i=n;i>0;i--)

    {

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

        {

            dp[i][j]=LLONG_MAX;

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

            {

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

            }

        }

    }

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



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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


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



using namespace std;



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

#define int long long                           //del this if TLE or MLE

#define ll long long

#define pr pair<int,int>

#define mp make_pair

#define pb push_back

#define eb emplace_back

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

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

#define F first

#define S second

#define loop int tests;cin>>tests;while(tests--)



const int N=405;

const int inf=1e18;



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



int DP(int i,int j)

{

	if(i==j) 

		return 0;

	if(i+1==j) 

		return a[i]+a[j];

	if(dp[i][j]!=0)

		return dp[i][j];

	int Min=inf;

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

	{

		int x=DP(i,k)+DP(k+1,j)+pre[k]-pre[i-1]+pre[j]-pre[k];

		if(x<Min) 

			Min=x;

	}

	return dp[i][j]=Min;

}



signed main()

{

	fastio;

	int n;

	cin>>n;

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

	{

		cin>>a[i];

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

 	}

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

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

using namespace std;

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

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 4e2 + 9, M = 1e5 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



ll mem[N][N], arr[N], pre[N];



ll solve(int start, int end) {

  if(start >= end)

    return 0;

  ll& ret =mem[start][end];

  if(~ret)

    return ret;

  ret = inf;

  for (int i = start; i < end; ++i) {

    ll c1 = solve(start, i);

    ll c2 = solve(i+1, end);

    ll sumL = pre[i] - pre[start - 1], sumR = pre[end] - pre[i];

    ret = min(ret, c1 + c2 + sumL + sumR);

  }

  return ret;

}



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  memset(mem, -1, sizeof mem);

  int n;

  cin >> n;

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

    cin >> arr[i], pre[i] += pre[i-1] + arr[i];

  cout << solve(1, n);

  return 0;

}


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



using namespace std;



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

#define int long long                           //del this if TLE or MLE

#define ll long long

#define pr pair<int,int>

#define mp make_pair

#define pb push_back

#define eb emplace_back

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

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

#define F first

#define S second

#define loop int tests;cin>>tests;while(tests--)



const int N=405;

const int inf=1e18;



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



int DP(int i,int j)

{

	if(i==j) 

		return 0;

	if(i+1==j) 

		return a[i]+a[j];

	if(dp[i][j]!=0)

		return dp[i][j];

	int Min=inf;

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

	{

		int x=DP(i,k)+DP(k+1,j)+pre[k]-pre[i-1]+pre[j]-pre[k];

		if(x<Min) 

			Min=x;

	}

	return dp[i][j]=Min;

}



signed main()

{

	fastio;

	int n;

	cin>>n;

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

	{

		cin>>a[i];

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

 	}

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

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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


// Faster C++ solution for the same problem (measured speedup: 2.508537164694887x):
// Author : Mohamed Sameh

#include <bits/stdc++.h>

#define pb push_back

#define f first

#define s second

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

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

#define SZ(a) (int)a.size()

#define Flush fflush(stdout);

typedef long long ll ;

using namespace std ;

int n;

const int N = 4e2+9;

int a[N];

ll dp[N][N];

ll pre[N];

ll sum (int l, int r)

{

  return pre[r] - (l - 1 >= 0 ? pre[l-1] : 0);

}

void test ()

{

   cin >> n;

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

    cin >> a[i];

   pre[0] = a[0];

   for (int i = 1; i < n; i++)pre[i] = pre[i-1] + a[i];

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

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

      dp[i][j] = (i != j ? 1e18 : 0);

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

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

   {

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

     {

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

       {

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

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

       }

    }

   }

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

}

int main()

{

  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  test();

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

using namespace std;

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

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 4e2 + 9, M = 1e5 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



ll mem[N][N], arr[N], pre[N];



ll solve(int start, int end) {

  if(start >= end)

    return 0;

  ll& ret =mem[start][end];

  if(~ret)

    return ret;

  ret = inf;

  for (int i = start; i < end; ++i) {

    ll c1 = solve(start, i);

    ll c2 = solve(i+1, end);

    ll sumL = pre[i] - pre[start - 1], sumR = pre[end] - pre[i];

    ret = min(ret, c1 + c2 + sumL + sumR);

  }

  return ret;

}



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  memset(mem, -1, sizeof mem);

  int n;

  cin >> n;

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

    cin >> arr[i], pre[i] += pre[i-1] + arr[i];

  cout << solve(1, n);

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.332754971306558x):
// Author : Mohamed Sameh

#include <bits/stdc++.h>

#define pb push_back

#define f first

#define s second

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

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

#define SZ(a) (int)a.size()

#define Flush fflush(stdout);

typedef long long ll ;

using namespace std ;

int n;

const int N = 4e2+9;

int a[N];

ll dp[N][N];

ll pre[N];

ll sum (int l, int r)

{

  return pre[r] - (l - 1 >= 0 ? pre[l-1] : 0);

}

void test ()

{

   cin >> n;

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

    cin >> a[i];

   pre[0] = a[0];

   for (int i = 1; i < n; i++)pre[i] = pre[i-1] + a[i];

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

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

      dp[i][j] = (i != j ? 1e18 : 0);

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

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

   {

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

     {

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

       {

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

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

       }

    }

   }

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

}

int main()

{

  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  test();

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

using namespace std;

#define N 440

typedef long long ll;

int n;

ll a[N],memo[N][N],ps[N];



void precompute() {

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

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

}



ll rsum(int l , int r) {

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

}



ll dp(int i , int j) {

    if (i > j) return INT_MAX;

    if (i == j) return 0;

    if (j - i == 1) return a[i] + a[j];

    ll &sol = memo[i][j];

    if (sol != -1) return sol;

    ll keep = LLONG_MAX;

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

        keep = min(

            dp(i , k) + dp(k + 1 , j) + rsum(i , j),

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d" , &n);

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

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

    memset (memo , -1 , sizeof memo);

    precompute();

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

}


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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long



const long long maxn = 4e2 + 5;

const long long inf = 999999999999999;



long long num[maxn];

long long dp[maxn][maxn];

long long pre[maxn];



int main(){

	long long n; cin >> n;

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

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

	}



	pre[1] = num[1];

	for(ll i = 2; i <= n; i++) pre[i] = pre[i-1] + num[i];



	ll r;



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

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

			r = i + l - 1;

			dp[l][r] = inf;

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

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

			}

		}

	}



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



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

using namespace std;

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

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 4e2 + 9, M = 1e5 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



ll mem[N][N], arr[N], pre[N];



ll solve(int start, int end) {

  if(start >= end)

    return 0;

  ll& ret =mem[start][end];

  if(~ret)

    return ret;

  ret = inf;

  for (int i = start; i < end; ++i) {

    ll c1 = solve(start, i);

    ll c2 = solve(i+1, end);

    ll sumL = pre[i] - pre[start - 1], sumR = pre[end] - pre[i];

    ret = min(ret, c1 + c2 + sumL + sumR);

  }

  return ret;

}



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  memset(mem, -1, sizeof mem);

  int n;

  cin >> n;

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

    cin >> arr[i], pre[i] += pre[i-1] + arr[i];

  cout << solve(1, n);

  return 0;

}


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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long



const long long maxn = 4e2 + 5;

const long long inf = 999999999999999;



long long num[maxn];

long long dp[maxn][maxn];

long long pre[maxn];



int main(){

	long long n; cin >> n;

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

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

	}



	pre[1] = num[1];

	for(ll i = 2; i <= n; i++) pre[i] = pre[i-1] + num[i];



	ll r;



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

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

			r = i + l - 1;

			dp[l][r] = inf;

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

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

			}

		}

	}



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



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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f

#define INF 0x3f3f3f3f3f3f3f3f

#define pb push_back

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

#define ms(a, x) memset(a, x, sizeof(a))

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

#define for1(i, n) for(int i = 1; i <= n; ++i)

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<long long, int> pli;

typedef pair<long long, long long> pll;

const int mod = 1e9 + 7;

const int N = 4e2 + 10;

const int M = 1e5 + 10;

/*=================================================================================*/



ll dp[N][N];

int n, a[N];



ll w(int i, int j) {

   ll ans = 0;

   for(int k = i; k <= j; ++k) ans+=a[k];

   return ans;

}



int main() {

   scanf("%d", &n);

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

   ms(dp, 0);

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

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

         int j = i+len-1;

         dp[i][j] = INF;

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

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

            // debug1 printf("%d %d %lld %lld %lld %lld\n", i, j, dp[i][j], dp[i][k], dp[k+1][j], w(i, j));

         }

      }

   }

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

}

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long



const long long maxn = 4e2 + 5;

const long long inf = 999999999999999;



long long num[maxn];

long long dp[maxn][maxn];

long long pre[maxn];



int main(){

	long long n; cin >> n;

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

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

	}



	pre[1] = num[1];

	for(ll i = 2; i <= n; i++) pre[i] = pre[i-1] + num[i];



	ll r;



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

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

			r = i + l - 1;

			dp[l][r] = inf;

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

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

			}

		}

	}



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



}