stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:


#include <iostream>

#include <climits>

#include <cstring>

#include <algorithm>



using namespace std;



#define SIZE 420

long long cost[SIZE][SIZE], a[SIZE];



long long minimalSum(int l, int r) {

    if (     l     >=  r) return 0;

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

    long long MIN = LLONG_MAX, sum = 0;

    for (int i = l; i <= r; i++) sum += a[i];

    for (int i = l; i <  r; i++) MIN = min(MIN, minimalSum(l  , i)

                                          +sum+ minimalSum(i+1, r));

    return cost[l][r] = MIN;

}



int main() {

    memset(cost, -1, sizeof cost);

    int N; cin >> N;

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

    cout << minimalSum(0, N-1) << endl;

    return 0;

}


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

using namespace std;



#define ll long long

#define endl "\n"



const ll INF = 2e18;



int n;

vector <int> slimes(405, 0);	



ll sum (int l, int r){

	ll sum = 0;

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

		sum += slimes[i];

	}



	return sum;

}



int main ()

{

	

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    #define int ll

	

	cin >> n;

	

	for (int i=1; i<=n; i++) cin >> slimes[i];



	vector <vector <int> > dp(n+1, vector <int> (n+1, INF));

	

	for (int left = n; left >= 1; left--){

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

			if (right < left) continue;

			if (left == right){

				dp[left][left] = 0;

				continue;

			}

			int summation = sum(left, right);

			for (int i=left; i<=right-1; i++){

				dp[left][right] = min(dp[left][right], dp[left][i] + dp[i+1][right] + summation);

			}

		}

	}



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



	return 0;

	

}
// Slower C++ solution:
// 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 solve(int l = 0, int r = n-1)

{

  if (l >= r)return 0;

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

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

  if (~ret)return ret;

  ret = 1e18;

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

  {

    ret = min(ret, solve(l, i) + solve(i+1, r) + a[l] + pre[r] - pre[l]);

  }

  return ret;

}

void test ()

{

  memset(dp, -1, sizeof dp);

  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];

  cout << solve() <<"\n";

}

int main()

{

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

  test();

}


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

using namespace std;



#define ll long long

#define endl "\n"



const ll INF = 2e18;



int n;

vector <int> slimes(405, 0);	



ll sum (int l, int r){

	ll sum = 0;

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

		sum += slimes[i];

	}



	return sum;

}



int main ()

{

	

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    #define int ll

	

	cin >> n;

	

	for (int i=1; i<=n; i++) cin >> slimes[i];



	vector <vector <int> > dp(n+1, vector <int> (n+1, INF));

	

	for (int left = n; left >= 1; left--){

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

			if (right < left) continue;

			if (left == right){

				dp[left][left] = 0;

				continue;

			}

			int summation = sum(left, right);

			for (int i=left; i<=right-1; i++){

				dp[left][right] = min(dp[left][right], dp[left][i] + dp[i+1][right] + summation);

			}

		}

	}



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



	return 0;

	

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

#define lli long long

using namespace std;



vector<long long>vp;



long long dp[410][410];

long long dpp(int i,int j)



{

  if(i>j)

  return 0;

  if(j==i)

  return 0;



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

  return dp[i][j];



 long long ans=1e20;

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

  {

    ans=min(ans,vp[j]-vp[i-1]+dpp(i,x)+dpp(x+1,j));

  }



return dp[i][j]=ans;

}

int main()

{



    memset(dp,-1,sizeof dp);

    int n;

    cin>>n;

    long long sum=0;

    vp.push_back(0);

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

    {

      int a;

      cin>>a;

      sum+=a;

      vp.push_back(sum);



    }

    cout <<dpp(1,n);

}










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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

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

using namespace std;

long long n,a[410],dp[410][410],pref[410];

long long f(long long l,long long r)

{

//	printf("%lld %lld\n",l,r);

	if(r<=l || l>=r) return 0;

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

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

	{

	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);

		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 

		else dp[l][r] = min(dp[l][r],f(l,i)+f(i+1,r));

	}

	return dp[l][r]+=pref[r]-pref[l-1];

}

int main()

{

	scanf("%lld",&n);

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

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

	{

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

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

	}	

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

//	printf("c : \n");

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

//	{

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

//		{

//			printf("%d %d %lld\n",i,j,dp[i][j]);

//		}

//	}

	return 0;

}

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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 4e2+5;



const int mod = 1e9+7;



int n;

int ar[N];

long long prefix[N];

long long mem[N][N];



long long getsum(int l , int r){

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

}



long long go(int l , int r){

    if(r - l + 1 == 2)

        return getsum(l , r);

    if(l >= r)

        return 0;

    if(~mem[l][r])

        return mem[l][r];

    long long best = 1e18;

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

        best = min(best , go(l , i) + go(i + 1 , r) + getsum(l , i) + getsum(i + 1 , r));

    }

    return mem[l][r] = best;

}



int main(){

    scanf("%d" , &n);

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

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

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

    }

    memset(mem , -1 , sizeof mem);

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

}


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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

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

using namespace std;

const int N = 2e4 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;

const long long OO = 1e18+25;

#define par pair<pair<int,int>, int>

#define f first

#define s second



int n, a[405];

long long mem[405][405],cum[405];



long long dp(int start=1, int end=n)

{

    if(start == end) return 0;

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

    if(~ret) return ret;

    ret = OO;

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

    {

        ret = min(ret,1ll* dp(start, i)+dp(i+1, end)+(cum[i]-cum[start-1])+(cum[end]-cum[i]));

    }

    return ret;

}



int main()

{

    memset(mem, -1, sizeof mem);

    scanf("%d",&n);

    for(int i=1; i<=n ;i++)scanf("%d",a+i);

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

    printf("%lld",dp());

    return 0;

}

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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

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

using namespace std;

#define endl '\n'

long long arr[401];

int n;

long long dp[401][401];

long long f(int l,int r){

	if(l==r)return 0;

	long long &mi=dp[l][r];

	if(~mi)return mi;

	mi=1000000000000000000LL;

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

		mi=min(mi,f(l,i)+f(i+1,r)+arr[r]-arr[l-1]);

	}

	return mi;

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	memset(dp,-1,sizeof dp);



	cin>>n;

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

		cin>>arr[i];

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

	}





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



	return 0;

}

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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

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



using namespace std;



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

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

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

#define ll long long

#define pb					push_back

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



const ll oo = 1e8;

const double pi = 3.1415926535897;





const double EPS = (1e-7);

int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}





typedef vector<int>                vi;

typedef vector<pair<int,int>>      vii;

typedef vector<ll>                 vll;

typedef vector<double>             vd;

typedef vector< vi >               vvi;

typedef vector< vd >               vvd;

typedef vector<string>             vs;

typedef pair<int, int>             pii;



/**

    * PLEASEEE READDD PROBLEEEM CARFULLY ****

    * Always check for OVERFLOW ll vs int

    * Always check for array bounds

    * Check for function return

    * READ OUTPUT SECTION AGAIN!!!

**/



struct edge{

    int from, to, w;



    edge(){}

    edge(int x, int y, int we): from(x), to(y), w(we){}



    bool operator < (const edge &rhs) const{

        return w > rhs.w;

    }



};



const int N = 400 + 5;



ll dp[N][N];

ll pre[N];

int a[N];



ll sol(int l ,int r) {

    if(l == r) return 0;



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

    if(ret != -1) return ret;



    ret = 1e18L;

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

        ret = min(ret, sol(l, i) + sol(i + 1, r) + pre[r + 1] - pre[l]);

    }



    return ret;

}







int main(){

    fIO

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

//    freopen("", "w", stdout);



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



    int n;

    cin >> n;



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



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



    cout << sol(0, n - 1) << "\n";

}














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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

}
// Slower C++ solution:


#include <iostream>

#include <climits>

#include <cstring>

#include <algorithm>



using namespace std;



#define SIZE 420

long long cost[SIZE][SIZE], a[SIZE];



long long minimalSum(int l, int r) {

    if (     l     >=  r) return 0;

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

    long long MIN = LLONG_MAX, sum = 0;

    for (int i = l; i <= r; i++) sum += a[i];

    for (int i = l; i <  r; i++) MIN = min(MIN, minimalSum(l  , i)

                                          +sum+ minimalSum(i+1, r));

    return cost[l][r] = MIN;

}



int main() {

    memset(cost, -1, sizeof cost);

    int N; cin >> N;

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

    cout << minimalSum(0, N-1) << endl;

    return 0;

}


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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

}
// Slower C++ solution:
// 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 solve(int l = 0, int r = n-1)

{

  if (l >= r)return 0;

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

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

  if (~ret)return ret;

  ret = 1e18;

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

  {

    ret = min(ret, solve(l, i) + solve(i+1, r) + a[l] + pre[r] - pre[l]);

  }

  return ret;

}

void test ()

{

  memset(dp, -1, sizeof dp);

  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];

  cout << solve() <<"\n";

}

int main()

{

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

  test();

}


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

using namespace std;

typedef long long ll;

ll dp[410][410],sum[410][410];

ll p,c1,c2;



ll solve(ll i,ll j,ll a[])

{

    if(i>=j){

        dp[i][j]=0;

        return a[i];}

    if(i+1==j)

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

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

        return sum[i][j];

    ll ans=9999999999999999999999,s1=0,s2=0,a1=0;

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

            a1=0;

        s1=solve(i,k,a);

        s2=solve(k+1,j,a);

        a1=s1+s2+dp[i][k]+dp[k+1][j];

        ans=min(ans,a1);

        a1=s1+s2;

    }

    dp[i][j]=ans;

    sum[i][j]=a1;

    return a1;

}



int main()

{

    ll n,i,j,k;

    cin>>n;

    ll a[n+1];

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

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

            dp[i][j]=-1;

            sum[i][j]=-1;

        }

    }

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

        cin>>a[i];

    ll s=solve(1,n,a);

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

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

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

        }cout<<endl;

    }*/

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

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

#define lli long long

using namespace std;



vector<long long>vp;



long long dp[410][410];

long long dpp(int i,int j)



{

  if(i>j)

  return 0;

  if(j==i)

  return 0;



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

  return dp[i][j];



 long long ans=1e20;

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

  {

    ans=min(ans,vp[j]-vp[i-1]+dpp(i,x)+dpp(x+1,j));

  }



return dp[i][j]=ans;

}

int main()

{



    memset(dp,-1,sizeof dp);

    int n;

    cin>>n;

    long long sum=0;

    vp.push_back(0);

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

    {

      int a;

      cin>>a;

      sum+=a;

      vp.push_back(sum);



    }

    cout <<dpp(1,n);

}










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

#include<cstring>

#define ll long long

#define pi acos(-1.0)

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 2e5+5;

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

int n;



ll dfs(int l, int r){

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

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

	ll res = 1e17;

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

		res = min(res, dfs(l, i) + dfs(i+1, r));

	}

	return dp[l][r] = res + pre[r] - pre[l-1];

}



int main(){

	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dfs(1, n) - pre[n] << endl;

	return 0;

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

using namespace std;

long long n,a[410],dp[410][410],pref[410];

long long f(long long l,long long r)

{

//	printf("%lld %lld\n",l,r);

	if(r<=l || l>=r) return 0;

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

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

	{

	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);

		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 

		else dp[l][r] = min(dp[l][r],f(l,i)+f(i+1,r));

	}

	return dp[l][r]+=pref[r]-pref[l-1];

}

int main()

{

	scanf("%lld",&n);

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

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

	{

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

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

	}	

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

//	printf("c : \n");

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

//	{

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

//		{

//			printf("%d %d %lld\n",i,j,dp[i][j]);

//		}

//	}

	return 0;

}

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

#include<cstring>

#define ll long long

#define pi acos(-1.0)

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 2e5+5;

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

int n;



ll dfs(int l, int r){

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

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

	ll res = 1e17;

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

		res = min(res, dfs(l, i) + dfs(i+1, r));

	}

	return dp[l][r] = res + pre[r] - pre[l-1];

}



int main(){

	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dfs(1, n) - pre[n] << endl;

	return 0;

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 4e2+5;



const int mod = 1e9+7;



int n;

int ar[N];

long long prefix[N];

long long mem[N][N];



long long getsum(int l , int r){

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

}



long long go(int l , int r){

    if(r - l + 1 == 2)

        return getsum(l , r);

    if(l >= r)

        return 0;

    if(~mem[l][r])

        return mem[l][r];

    long long best = 1e18;

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

        best = min(best , go(l , i) + go(i + 1 , r) + getsum(l , i) + getsum(i + 1 , r));

    }

    return mem[l][r] = best;

}



int main(){

    scanf("%d" , &n);

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

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

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

    }

    memset(mem , -1 , sizeof mem);

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

}


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

#include<cstring>

#define ll long long

#define pi acos(-1.0)

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 2e5+5;

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

int n;



ll dfs(int l, int r){

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

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

	ll res = 1e17;

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

		res = min(res, dfs(l, i) + dfs(i+1, r));

	}

	return dp[l][r] = res + pre[r] - pre[l-1];

}



int main(){

	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dfs(1, n) - pre[n] << endl;

	return 0;

}