stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.6714400442292145x):
#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;

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

using namespace std;

int main()

{

     int x,y;

      cin>>x>>y;

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

        cout<<"Yay!";

      else

        cout<<":(";



}


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

int main()

{

    int a,b;

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

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

    else printf(":(\n");

}
// Slower C++ solution:
#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;

}


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

int main()

{

    int a,b;

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

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

    else printf(":(\n");

}
// Slower C++ solution:
#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";

}

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

int main()

{

    int a,b;

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

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

    else printf(":(\n");

}
// Slower C++ solution:
#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;

}

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

int main()

{

    int a,b;

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

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

    else printf(":(\n");

}
// Slower C++ solution:
#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;

    }















}






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

int main(){

int a,b ;

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

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

else printf(":(") ;return 0;}
// Slower C++ solution:
#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;

}

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

int main(){

int a,b ;

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

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

else printf(":(") ;return 0;}
// Slower C++ solution:
#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;

}

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

int main(){

int a,b ;

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

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

else printf(":(") ;return 0;}
// Slower C++ solution:
#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;

}














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

int main(){

int a,b ;

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

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

else printf(":(") ;return 0;}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.295585840400236x):
#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;

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

#include <vector>

#include <limits.h>

#include <algorithm>

#include <string>

#include <math.h>

#include <limits.h>

#include <queue>

#include <map>

#include <set>

#include <iomanip>

#include <bitset>

#include <cassert>

#include <random>

#include <functional>

#include <stack>

#include <iomanip>

using namespace std;

int MOD = 1e9 + 7;



int N;

vector<long long> A;



vector<vector<long long>> DP;

vector<long long> AA;



int main() {

	cin >> N;

	A.resize(N);

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

		cin >> A[n];

	}

	AA.resize(N+1);

	DP.resize(N, vector<long long>(N, LLONG_MAX));

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

		AA[n] = AA[n - 1] + A[n - 1];

		DP[n - 1][n - 1] = 0;

	}

	for (int n = 0; n < N - 1; n++) {

		DP[n][n + 1] = A[n] + A[n + 1];

	}

	for (int k = 2; k < N; k++) {

		for (int left = 0; left < N; left++) {

			int right = left + k;

			if (right >= N)continue;

			for (int mid = left; mid < right; mid++) {

				DP[left][right] = min(DP[left][right] ,DP[left][mid]+DP[mid+1][right]+ AA[right + 1] - AA[left]);

			}

		}

	}

	cout << DP[0][N - 1] << 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.3054197019176152x):
#include <iostream>

#include <vector>

#include <limits.h>

#include <algorithm>

#include <string>

#include <math.h>

#include <limits.h>

#include <queue>

#include <map>

#include <set>

#include <iomanip>

#include <bitset>

#include <cassert>

#include <random>

#include <functional>

#include <stack>

#include <iomanip>

using namespace std;

int MOD = 1e9 + 7;



int N;

vector<long long> A;



vector<vector<long long>> DP;

vector<long long> AA;



int main() {

	cin >> N;

	A.resize(N);

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

		cin >> A[n];

	}

	AA.resize(N+1);

	DP.resize(N, vector<long long>(N, LLONG_MAX));

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

		AA[n] = AA[n - 1] + A[n - 1];

		DP[n - 1][n - 1] = 0;

	}

	for (int n = 0; n < N - 1; n++) {

		DP[n][n + 1] = A[n] + A[n + 1];

	}

	for (int k = 2; k < N; k++) {

		for (int left = 0; left < N; left++) {

			int right = left + k;

			if (right >= N)continue;

			for (int mid = left; mid < right; mid++) {

				DP[left][right] = min(DP[left][right] ,DP[left][mid]+DP[mid+1][right]+ AA[right + 1] - AA[left]);

			}

		}

	}

	cout << DP[0][N - 1] << 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.2927401148751847x):
#include <bits/stdc++.h>

#define ll long long

#define ull unsigned ll

#define ld long double

#define pll pair<ll, ll>

#define pii pair<int, int>

#define f first

#define se second

#define pb push_back

#define ft fflush(stdout)

 

 

using namespace std;

 

 

const int N = 523;

const int PLS = 3e5 + 123;

const ll mod = 1e9 + 7;

const ll inf = 1e16;





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

bool vis[N][N];





ll get(ll l, ll r) {

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

}





void rec(ll l, ll r) {

    if (vis[l][r])

        return;

    vis[l][r] = 1;

    if (l == r) {

        dp[l][r] = 0;

        return;

    }

    dp[l][r] = inf;

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

        rec(l, i);

        rec(i + 1, r);

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

    }

}





int main() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

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

        cin >> a[i];

    p[0] = 0;

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

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

    rec(1, n);

    cout << dp[1][n];

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

#define ll long long

#define ull unsigned ll

#define ld long double

#define pll pair<ll, ll>

#define pii pair<int, int>

#define f first

#define se second

#define pb push_back

#define ft fflush(stdout)

 

 

using namespace std;

 

 

const int N = 523;

const int PLS = 3e5 + 123;

const ll mod = 1e9 + 7;

const ll inf = 1e16;





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

bool vis[N][N];





ll get(ll l, ll r) {

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

}





void rec(ll l, ll r) {

    if (vis[l][r])

        return;

    vis[l][r] = 1;

    if (l == r) {

        dp[l][r] = 0;

        return;

    }

    dp[l][r] = inf;

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

        rec(l, i);

        rec(i + 1, r);

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

    }

}





int main() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

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

        cin >> a[i];

    p[0] = 0;

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

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

    rec(1, n);

    cout << dp[1][n];

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

#include <ext/pb_ds/assoc_container.hpp> // Common file

#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

#include <ext/pb_ds/detail/standard_policies.hpp>



using namespace std;

using namespace __gnu_pbds;



typedef tree<int, null_type, less<int>, rb_tree_tag,

		tree_order_statistics_node_update> ordered_set;



#define el				'\n'

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

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

#define clr(v, d)		memset(v, d, sizeof(v))



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

const int N = 405 + 9, M = 100 + 9, OO = (int) 1e9 + 1;

const long long MOD = 1e9 + 7, INF = 1e18 + 9;



typedef long long ll;



void OUTPUT() {

	cout << fixed << setprecision(12);

	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

}



void INPUT() {

#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);

//	freopen("output.txt", "w", stdout);

#endif

}

int n, arr[N];

ll dp[N][N], cum[N];

int main() {

//	INPUT();

	OUTPUT();

	cin >> n;

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

		cin >> arr[i];

		cum[i] = arr[i] + cum[i - 1] * (i != 0);

	}

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

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

			if (L == R)

				dp[L][R] = 0;

			else {

				dp[L][R] = INF;

				ll s = cum[R];

				if (L != 0)

					s -= cum[L - 1];

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

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

				}

			}

		}

	}

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



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

#include <ext/pb_ds/assoc_container.hpp> // Common file

#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

#include <ext/pb_ds/detail/standard_policies.hpp>



using namespace std;

using namespace __gnu_pbds;



typedef tree<int, null_type, less<int>, rb_tree_tag,

		tree_order_statistics_node_update> ordered_set;



#define el				'\n'

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

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

#define clr(v, d)		memset(v, d, sizeof(v))



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

const int N = 405 + 9, M = 100 + 9, OO = (int) 1e9 + 1;

const long long MOD = 1e9 + 7, INF = 1e18 + 9;



typedef long long ll;



void OUTPUT() {

	cout << fixed << setprecision(12);

	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

}



void INPUT() {

#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);

//	freopen("output.txt", "w", stdout);

#endif

}

int n, arr[N];

ll dp[N][N], cum[N];

int main() {

//	INPUT();

	OUTPUT();

	cin >> n;

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

		cin >> arr[i];

		cum[i] = arr[i] + cum[i - 1] * (i != 0);

	}

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

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

			if (L == R)

				dp[L][R] = 0;

			else {

				dp[L][R] = INF;

				ll s = cum[R];

				if (L != 0)

					s -= cum[L - 1];

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

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

				}

			}

		}

	}

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



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

#include <unordered_map>

#include <unordered_set>

using namespace std;

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

//	Table is the complete reverse of dp

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

//	Be careful of unsigned

//	double epsilon = FLT_EPSILON;

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

int n;

ll **dp, *x;



int main()

{

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

    cin >> n;

    x = new ll[n];

    dp = new ll *[n];

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

    {

    	cin >> x[i];

    	dp[i] = new ll[n];

    	dp[i][i] = 0;

    	if(i)

    	{

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

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

    	}

    }

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

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

    	{

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

    		ret = 1e16;

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

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

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

    	}

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

}