stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <fstream>

#include <utility>

#include <iomanip>

#include <cstring>

#include <string>

#include <sstream>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>

#define IO ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;

typedef long double ld;



using namespace std;

const ll INF = 1e18;

const int mod = 1e4, N = 1e5 + 5, inf = 1e9;



int main()

{

    IO

    int n, a[N], b[N], c[N];

    ll ans[N][2] = {}; // :)

    ll A = 0; // :)

    cin >> n;

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

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

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

    sort(a, a + n);

    sort(b, b + n);

    sort(c, c + n);

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

    {

        int s = 0, e = n - 1, m, loc = -1;

        while(s <= e)

        {

            m = (s + e) / 2;

            if(a[m] < b[i])

            {

                loc = m;

                s = m + 1;

            }

            else e = m - 1;

        }

        ans[i][0] = loc + 1;

    }

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

        ans[i][0] += ans[i - 1][0];

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

    {

        int s = 0, e = n - 1, m, loc = -1;

        while(s <= e)

        {

            m = (s + e) / 2;

            if(b[m] < c[i])

            {

                loc = m;

                s = m + 1;

            }

            else e = m - 1;

        }

        if(loc != -1)

            ans[i][1] = ans[loc][0];

    }

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

        A += ans[i][1];

    cout << A << '\n';

    return 0;

}

// Optimized solution to the same problem (faster):
#include<math.h>

#include<algorithm>

#include <iostream>

using namespace std;

typedef long long int LL;

const int N=1e5+5;

int a[N];

int b[N];

int c[N];

int main()

{

int n;

cin>>n;

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

	cin>>a[i];

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

	cin>>b[i];

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

	cin>>c[i];

sort(a,a+n);

sort(b,b+n);

sort(c,c+n);

LL j=0;//用于统计第一部分里面小于第二部分的个数

LL k=0;//用于统计第三部分里面小于第二部分的个数

LL sum=0;

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

	while(a[j]<b[i]&&j<n){

	j++;

	}

	while(c[k]<=b[i]&&k<n){

	k++;

	}

	sum+=(j*(n-k));

}

 

cout<<sum<<endl;

 

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

     int x,y;

      cin>>x>>y;

      if(x<=8&&y<=8)

        cout<<"Yay!";

      else

        cout<<":(";



}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b;

    scanf("%d %d",&a,&b);

    if( a<9 && b<9) printf("Yay!\n");

    else printf(":(\n");

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define  ll  long long

#define  sf  scanf

#define  pf  printf

int main()

{

    int t,z,i,n,m;

    sf("%d %d",&n,&m);

    if(n>8 || m>8)

    {

        pf(":(\n");

    }

    else

    {

        pf("Yay!\n");

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b;

    scanf("%d %d",&a,&b);

    if( a<9 && b<9) printf("Yay!\n");

    else printf(":(\n");

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int a, b;

    cin >> a >> b;

    if(a > 8 || b > 8) cout << ":(\n";

    else cout << "Yay!\n";

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b;

    scanf("%d %d",&a,&b);

    if( a<9 && b<9) printf("Yay!\n");

    else printf(":(\n");

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>



using namespace std;



int main(){

	int a, b, cake[16];

	cin>>a;

	cin>>b;

	if((a+b)>16)

		cout<<":("<<endl;

	if(a>8||b>8){

		cout<<":("<<endl;

	}

	

	else{

		cout<<"Yay!"<<endl;

	}





return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b;

    scanf("%d %d",&a,&b);

    if( a<9 && b<9) printf("Yay!\n");

    else printf(":(\n");

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



int main ()

{

    long long int a,b,s,m,su,xx;



    cin >> a>>b ;



    if (a<=8 && b<=8 && a+b<=16)

    {

        cout << "Yay!"<<endl;

    }



    else

    {

        cout << ":("<<endl;

    }















}






// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){

int a,b ;

scanf("%d%d",&a,&b);

if(a<=8 && b<=8)printf("Yay!");

else printf(":(") ;return 0;}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int A, B;



    cin>>A>>B;



    if(A > 8 || B > 8){



            cout<<":("<<endl;

    }

    else{

        cout<<"Yay!"<<endl;

    }



    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){

int a,b ;

scanf("%d%d",&a,&b);

if(a<=8 && b<=8)printf("Yay!");

else printf(":(") ;return 0;}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



int main ()

{

    int a, b;

    cin >> a >> b;

    int maior = max(a, b);

    if (maior > 8)

        cout << ":(";

    else

        cout << "Yay!";

    cout << endl;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){

int a,b ;

scanf("%d%d",&a,&b);

if(a<=8 && b<=8)printf("Yay!");

else printf(":(") ;return 0;}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



/*** Typedef ***/

typedef long long ll;

typedef unsigned long long ull;



/*** Loops ***/

#define ffit(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

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

#define ff2(i,a,b) for(ll i = b-1; i >= a; i--)

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

#define ipar(ar,n) ll ar[n]; ff1(i,0,n) cin>>ar[i];

#define opar(ar,n) ff1(i,0,n) cout<<ar[i]<<" ";

#define foRev(num) for(ll i = num - 1; i >= 0; i--)

#define forIn(arr, num) for(ll i = 0; i < num; i++) sc1(arr[i]);

#define forIn1(arr, num) for(ll i = 1; i <= num; i++) sc1(arr[i]);

#define vpnt(ans) for(ll i = 0; i < ans.size(); i++) cout << ans[i] << (i + 1 < ans.size() ? ' ' : '\n');

#define apnt(arr, num) for(ll i = 0; i < num; i++) cout << arr[i] << (i + 1 < num ? ' ' : '\n');



/*** Define Values ***/

//#define mod 1000000007

#define PI acos(-1.0)

#define eps 1e-7

#define size1 15



/*** STLs ***/

#define rsz(x...) resize(x)

#define ins(x...) insert(x)

#define ft() front()

#define bk() back()

#define eb(x...) emplace_back(x)

#define lb(x...) lower_bound(x)

#define ub(x...) upper_bound(x)

#define pb push_back

#define ff first

#define ss second

#define mp make_pair

#define mem(name, value) memset(name, value, sizeof(name))

#define endl " \n"



/*** STLs ***/

typedef vector <ll> vll;

#define vvll vector<vll>

typedef set <ll> sll;

typedef multiset <ll> msll;

typedef queue <ll> qll;

typedef map <ll, ll> mll;

typedef pair <ll, ll> pll;

typedef vector <pair <ll, ll> > vpll;



///vector<vector<int>> v(10, vector<int>(20,500)); 2d vector initialization. of 10 rows and 20 columns, with value 500.



/*** Sorts ***/

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

#define rev(v) reverse(all(v))

#define srt(v) sort(all(v))

#define srtgrt(v) sort(all(v), greater<ll>())

#define prsrt greater<pair<int,int>>()

/*** Some Prints ***/

#define q2(n) (n%2)==0

#define ip(n) ll n; cin>>n;

#define en cout << '\n';

#define no cout << "NO" << '\n'

#define yes cout << "YES" << '\n'

#define case cout << "Case " << t++ << ": ";

#define ps(x,y)         fixed<<setprecision(y)<<x

#define inf             1e18

#define debug(x) cout << '>' << #x << ':' << x << endl;

//const ll N = 1e6 + 9;

#define w(x)             ll x; cin>>x; while(x--)

//#define SIZE_INT sizeof(int) * 4



int main()

{

    ip(n);ip(m);

    if(n<=8 && m<=8)

    {

        cout<<"Yay!";

    }

    else cout<<":(";

return 0;

}














// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){

int a,b ;

scanf("%d%d",&a,&b);

if(a<=8 && b<=8)printf("Yay!");

else printf(":(") ;return 0;}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define ll          long long int

#define pb          push_back

#define pll         pair<ll,ll>

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

#define mode        998244353

#define mod         1000000007

#define inf         1000000000000000000LL

#define vl          vector<ll>

#define F           first

#define S           second

#define db          long double

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

#define fix(n)      cout<<fixed<<setprecision(n)

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

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

#define mset(x)     memset(x,0,sizeof x)

#define pi          3.14159265358979323



ll dp[404][404], a[404], sum[404];



ll f(ll l, ll r)

{

       if(l==r) return 0;

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

       if(ans!=-1) return ans;

       ans = inf;

       ll s = sum[r] - sum[l-1];

       rep(i, l, r)

              ans = min(ans, f(l, i)+f(i+1, r)+ s);

       return ans;

}



void solve()

{

       ll n;

       cin>>n;

       rep(i,1,n+1) cin>>a[i];

       sum[0]=0;

       rep(i,1,n+1) sum[i] = sum[i-1]+a[i];

       memset(dp, -1, sizeof dp);

       cout<<f(1, n);

}



int main() {

	ll T = 1;

	speed_up

	//cin>>T;

	while(T--)

	    solve();

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define ll          long long int

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

#define mod         1000000007

#define F           first

#define S           second

#define ld          long double

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

 

void solve()

{

    ll n; cin>>n;

    ll a[n+1];

    for(ll i=1; i<=n; i++) cin>>a[i];

    ll dp[n][n];

    ll sum[n+1];

    memset(sum, 0, sizeof sum);

    for(ll i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];

    for(ll L=n-1; L>=0; L--) {

        for(ll R=L; R<n; R++) {

            if(L==R) {

                dp[L][R] = 0;

            } else {

                ll s = sum[R+1] - sum[L];

                dp[L][R] = 1e15+5;

                for(ll i=L; i<R; i++) {

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

                }

            }

        }

    }

    ll ans = dp[0][n-1];

    cout<<ans<<endl;

}



int main() {

	ll T = 1;

	speed_up

	//cin>>T;

	while(T--)

	    solve();

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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';

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

#define ll long long

#define vi vector<ll>

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

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

#define tr(it, a)   for(auto it=a.begin();it!=a.end();it++)

#define pb push_back

#define endl  "\n"

const ll MAX=1e5+5;

const ll mod=1e9+7;

vi v(MAX);

vi pref(MAX);

ll dp[405][405];

ll  fun(ll i,ll k)

{

    if(k==i)

        return 0;

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

            return dp[i][k];

    ll ans=1e18;

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

    {

        ans=min(ans,fun(i,j)+fun(j+1,k)+pref[k]-pref[i-1]);

        // cout<<j<<"--> "<<ans<<endl;

    }



    return dp[i][k]=ans;

}

int main()

{

    ll t=1;

   // cin>>t;

    while(t--)

    {



   ll n,k;

   cin>>n;

   pref[0]=0;

   rep(i,1,n+1)

   {

       cin>>v[i];

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



   }

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

   cout<<fun(1,n);

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define ll long long

#define vi vector<ll>

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

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

#define tr(it, a)   for(auto it=a.begin();it!=a.end();it++)

#define pb push_back

#define endl  "\n"

const ll MAX=1e5+5;

const ll mod=1e9+7;

vi v(MAX);

vi pref(MAX);

ll dp[405][405];

/*

ll  fun(ll i,ll k)

{

    if(k==i)

        return 0;

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

            return dp[i][k];

    ll ans=1e18;

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

    {

        ans=min(ans,fun(i,j)+fun(j+1,k)+pref[k]-pref[i-1]);

    }

    return dp[i][k]=ans;

}*/

ll fun(ll n)

{

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

        dp[i][i]=0;

    for(ll len=2;len<=n;len++)

    {

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

        {

            ll val=1e18;

            for(ll k=i;k<=i+len-2;k++)

            {

                val=min(val,dp[i][k]+dp[k+1][i+len-1]+pref[i+len-1]-pref[i-1]);

            }

            dp[i][i+len-1]=val;

        }

    }

    /*

    rep(i,1,n+1)

    {

        rep(j,1,n+1)

        {

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

        }

        cout<<endl;

    }*/

    return dp[1][n];

}

int main()

{

    ll t=1;

   // cin>>t;

    while(t--)

    {



   ll n,k;

   cin>>n;

   pref[0]=0;

   rep(i,1,n+1)

   {

       cin>>v[i];

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



   }

   cout<<fun(n);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;



using ll = long long;

using P = pair<int, int>;



template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}

template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}



constexpr int MOD = 1e9 + 7;

constexpr ll INF = 1e18;

constexpr double pi = acos(-1);

constexpr double EPS = 1e-10;



int dx[] = {1, 0, -1, 0};

int dy[] = {0, -1, 0, 1};



vector<ll> sum(410);

vector<vector<ll>> dp(410, vector<ll>(410, -1));



// [l, r)

ll solve(int l, int r){

    if(0 <= dp[l][r]) return dp[l][r];

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



    ll val = INF;

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

        // [l, r) -> [l, i) and [i, r)

        ll cost = sum[r] - sum[l];

        chmin(val, solve(l, i) + solve(i, r) + cost);

    }



    return dp[l][r] = val;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n; cin>>n;

    vector<int> a(n);

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

        cin>>a[i];

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

    }



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

}

// Optimized solution to the same problem (faster):
#pragma GCC optimize("O3")

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <string>

#include <cstring>

#include <deque>

#include <list>

#include <queue>

#include <stack>

#include <vector>

#include <utility>

#include <algorithm>

#include <map>

#include <set>

#include <complex>

#include <cmath>

#include <limits>

#include <cfloat>

#include <climits>

#include <ctime>

#include <cassert>

#include <numeric>

#include <fstream>

#include <functional>

#include <bitset>

using namespace std;



using ll = long long;

using P = pair<int, int>;

using T = tuple<int, int, int>;



template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}

template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}



constexpr int MOD = 1e9 + 7;

constexpr int inf = 1e9;

constexpr long long INF = 1e18;



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



int dx[] = {1, 0, -1, 0};

int dy[] = {0, 1, 0, -1};



vector<ll> sum(410);

vector<vector<ll>> dp(410, vector<ll>(410));



ll solve(int l, int r){

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

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



    ll ans = INF;

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

        ll cost = sum[r] - sum[l];

        chmin(ans, solve(l, i) + solve(i, r) + cost);

    }



    return dp[l][r] = ans;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n; cin>>n;

    vector<int> a(n);

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



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



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



    return 0;

}

// Fastest known solution for this problem: