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

// You are not prepared!

 

#include <bits/stdc++.h>

using namespace std;

 

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }

template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {

  while(*sdbg!=',')cerr<<*sdbg++;

  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);

}

#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

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

typedef long long ll;



const int N = 407;

const ll INF = 1e18L+7;



int32_t main() {

	_upgrade

	

	int n; cin >> n;

	vector<int> a(n);

	for (int& x : a) {

		cin >> x;

	}

	

	vector<vector<ll>> dp(N, vector<ll>(N, 0));

	

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

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

			if (r == l) {

				dp[l][r] = 0;

			}

			else {

				dp[l][r] = INF;

				

				ll sum = 0;

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

					sum += a[i];

				}

				

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

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

				}

			}

		}

	}

	

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

}


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

#include<vector>

using namespace std;



int main()

{

	int n;

	cin>>n;

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

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

	{

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

	}

	vector< vector<long long> >dp;

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

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

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

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

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

	{

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

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

		{

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

		}

	}

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

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

#define pb push_back

#define x first 

#define y second

#define vec vector

#define ll long long

#define mp make_pair

#define pii pair<ll ,ll >

#define THICC 6942091166600000

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

#define loop(it) for(auto it = mep.begin();it!=mep.end();++it)

using namespace std;

int main(){

    int n;

    cin>>n;

    vector<ll> arr(420);

	vector<ll> pref(420);

    vector<vector<ll>> dp(666,vector<ll>(420 , 0));

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

		cin>>arr[i];

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

	}

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

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

			int l = j , r = j+i;

			dp[l][r] = THICC;

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

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

			}

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

        }

	}

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

}

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

#include<vector>

using namespace std;



int main()

{

	int n;

	cin>>n;

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

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

	{

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

	}

	vector< vector<long long> >dp;

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

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

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

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

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

	{

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

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

		{

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

		}

	}

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

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

/*                   وتزودوا فإن خير الزاد التقوى                    */

/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */

#include <bits/stdc++.h>

#include<unordered_map>

using namespace std;

#define endl '\n'

#define ll long long

#define PI acos(-1)

#define watch(x) cerr<<#x<<" = { "<<x<<" }\n"

#define sz(n) n.size();

#define Mo7med_Sayed fast();

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

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

#define RT(v) return cout<<v,0;

const double EPS = (1e-7);

const ll OO = INT_MAX, mod = 1e9 + 7;

void run() {

#ifndef ONLINE_JUDGE

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

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

#else

#endif

}

void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll n, m, k, t;

vector<ll>v;

ll dp[500][500];

ll solve(int l, int r) {

	if (l == r)return 0;

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

	if (~ret)return ret;

	ret = 1e17;

	ll s= (l ? v[l - 1] : 0);

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

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

	}

	return ret;

}

int main()

{

	//run();

	Mo7med_Sayed;

	cin >> n;

	v.resize(n);

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

		cin >> v[i];

		v[i] += (i ? v[i - 1] : 0);

	}

	memset(dp, -1, sizeof dp);

	RT(solve(0, n -1));

}


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

#include<vector>

using namespace std;



int main()

{

	int n;

	cin>>n;

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

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

	{

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

	}

	vector< vector<long long> >dp;

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

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

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

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

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

	{

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

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

		{

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

		}

	}

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

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<cmath>

#include<ctime>



using namespace std;

const int maxn = 1e5 + 7;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const double pi = acos(-1.0);

typedef long long ll;

#define pb push_back



int n;

ll a[405];

ll dp[405][405];

ll sum[405][405];



int main(){

	scanf("%d", &n);

	memset(dp, inf, sizeof dp);

	memset(sum, 0, sizeof sum);

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

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

		dp[i][i] = 0;

		sum[i][i] = a[i];

	}

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

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

			int j = i + len;

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

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

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

			}

		}

	}

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

}

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

#include<vector>

using namespace std;



int main()

{

	int n;

	cin>>n;

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

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

	{

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

	}

	vector< vector<long long> >dp;

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

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

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

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

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

	{

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

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

		{

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

		}

	}

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

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

#define ll long long

using namespace std;

const ll mod=1e9+7;

ll ps[100009],n,a[10009],dp[409][409];



ll f(ll l, ll r){

    if(l==r)return 0;

    ll tmp=1e17;

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

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

        tmp=min(tmp,f(l,i)+f(i+1,r)+ps[r]-ps[l-1]);

    }

    return dp[l][r]=tmp;

}



int main(){

    cin >> n;

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

        cin >> a[i];

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

    }

    memset(dp,-1,sizeof dp);

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

}

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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

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

using namespace std;



int const N=4e2+5, M=1e5+5, /*OO = 0x3f3f3f3f,*/ MOD=1e9+7;

long long const OO = 0x3f3f3f3f3f3f3f3f;

int n;

long long arr[N];



long long mem[N][N];

long long solve(int s, int e)

{

    if(s==e)

        return 0;

    if(mem[s][e]!=-1)

        return mem[s][e];

    long long ret=OO;

    for(int i=s; i<e; i++)

        ret=min(ret,solve(s,i)+solve(i+1,e)+arr[e]-arr[s-1]);

    return mem[s][e]=ret;

}





int main()

{

//    freopen("input.txt","rt",stdin);

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

    scanf("%d",&n);



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

    {

        scanf("%lld",arr+i);

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

    }

    memset(mem, -1, sizeof mem);

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





}


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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

}
// Slower C++ solution:
//TINY_OUNCE911666

// You are not prepared!

 

#include <bits/stdc++.h>

using namespace std;

 

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }

template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {

  while(*sdbg!=',')cerr<<*sdbg++;

  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);

}

#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

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

typedef long long ll;



const int N = 407;

const ll INF = 1e18L+7;



int32_t main() {

	_upgrade

	

	int n; cin >> n;

	vector<int> a(n);

	for (int& x : a) {

		cin >> x;

	}

	

	vector<vector<ll>> dp(N, vector<ll>(N, 0));

	

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

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

			if (r == l) {

				dp[l][r] = 0;

			}

			else {

				dp[l][r] = INF;

				

				ll sum = 0;

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

					sum += a[i];

				}

				

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

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

				}

			}

		}

	}

	

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

}


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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

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

#define pb push_back

#define x first 

#define y second

#define vec vector

#define ll long long

#define mp make_pair

#define pii pair<ll ,ll >

#define THICC 6942091166600000

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

#define loop(it) for(auto it = mep.begin();it!=mep.end();++it)

using namespace std;

int main(){

    int n;

    cin>>n;

    vector<ll> arr(420);

	vector<ll> pref(420);

    vector<vector<ll>> dp(666,vector<ll>(420 , 0));

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

		cin>>arr[i];

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

	}

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

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

			int l = j , r = j+i;

			dp[l][r] = THICC;

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

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

			}

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

        }

	}

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

}

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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

/*                   وتزودوا فإن خير الزاد التقوى                    */

/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */

#include <bits/stdc++.h>

#include<unordered_map>

using namespace std;

#define endl '\n'

#define ll long long

#define PI acos(-1)

#define watch(x) cerr<<#x<<" = { "<<x<<" }\n"

#define sz(n) n.size();

#define Mo7med_Sayed fast();

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

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

#define RT(v) return cout<<v,0;

const double EPS = (1e-7);

const ll OO = INT_MAX, mod = 1e9 + 7;

void run() {

#ifndef ONLINE_JUDGE

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

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

#else

#endif

}

void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll n, m, k, t;

vector<ll>v;

ll dp[500][500];

ll solve(int l, int r) {

	if (l == r)return 0;

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

	if (~ret)return ret;

	ret = 1e17;

	ll s= (l ? v[l - 1] : 0);

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

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

	}

	return ret;

}

int main()

{

	//run();

	Mo7med_Sayed;

	cin >> n;

	v.resize(n);

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

		cin >> v[i];

		v[i] += (i ? v[i - 1] : 0);

	}

	memset(dp, -1, sizeof dp);

	RT(solve(0, n -1));

}


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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<cmath>

#include<ctime>



using namespace std;

const int maxn = 1e5 + 7;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const double pi = acos(-1.0);

typedef long long ll;

#define pb push_back



int n;

ll a[405];

ll dp[405][405];

ll sum[405][405];



int main(){

	scanf("%d", &n);

	memset(dp, inf, sizeof dp);

	memset(sum, 0, sizeof sum);

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

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

		dp[i][i] = 0;

		sum[i][i] = a[i];

	}

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

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

			int j = i + len;

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

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

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

			}

		}

	}

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

}

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

using namespace std;

int n;

long  long a[405];

long long f[405][405],s[405];

int main()

{

	scanf("%d",&n);

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

	    scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];

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

	{

		int c=n-i+1;

		for(int j=1;j<=c;++j)

		{

			int l=j+i-1; 

			f[j][l]=f[j][j] + f[j+1][l];

			for(int k=j+1;k<=l;++k)

			  	f[j][l]=min(f[j][l],f[j][k]+f[k+1][l]);

			f[j][l]+=s[l]-s[j-1];

			//cout<<f[j][l]<<endl;

		} 

	}

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

	return 0;

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

#define ll long long

using namespace std;

const ll mod=1e9+7;

ll ps[100009],n,a[10009],dp[409][409];



ll f(ll l, ll r){

    if(l==r)return 0;

    ll tmp=1e17;

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

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

        tmp=min(tmp,f(l,i)+f(i+1,r)+ps[r]-ps[l-1]);

    }

    return dp[l][r]=tmp;

}



int main(){

    cin >> n;

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

        cin >> a[i];

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

    }

    memset(dp,-1,sizeof dp);

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

}

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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

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

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

	printf("%lld\n", DP(0, n - 1));

	return 0;

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

using namespace std;



int const N=4e2+5, M=1e5+5, /*OO = 0x3f3f3f3f,*/ MOD=1e9+7;

long long const OO = 0x3f3f3f3f3f3f3f3f;

int n;

long long arr[N];



long long mem[N][N];

long long solve(int s, int e)

{

    if(s==e)

        return 0;

    if(mem[s][e]!=-1)

        return mem[s][e];

    long long ret=OO;

    for(int i=s; i<e; i++)

        ret=min(ret,solve(s,i)+solve(i+1,e)+arr[e]-arr[s-1]);

    return mem[s][e]=ret;

}





int main()

{

//    freopen("input.txt","rt",stdin);

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

    scanf("%d",&n);



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

    {

        scanf("%lld",arr+i);

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

    }

    memset(mem, -1, sizeof mem);

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





}


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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

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

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

	printf("%lld\n", DP(0, n - 1));

	return 0;

}
// Slower C++ solution:
//TINY_OUNCE911666

// You are not prepared!

 

#include <bits/stdc++.h>

using namespace std;

 

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }

template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {

  while(*sdbg!=',')cerr<<*sdbg++;

  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);

}

#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

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

typedef long long ll;



const int N = 407;

const ll INF = 1e18L+7;



int32_t main() {

	_upgrade

	

	int n; cin >> n;

	vector<int> a(n);

	for (int& x : a) {

		cin >> x;

	}

	

	vector<vector<ll>> dp(N, vector<ll>(N, 0));

	

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

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

			if (r == l) {

				dp[l][r] = 0;

			}

			else {

				dp[l][r] = INF;

				

				ll sum = 0;

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

					sum += a[i];

				}

				

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

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

				}

			}

		}

	}

	

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

}


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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

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

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

	printf("%lld\n", DP(0, n - 1));

	return 0;

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

#define pb push_back

#define x first 

#define y second

#define vec vector

#define ll long long

#define mp make_pair

#define pii pair<ll ,ll >

#define THICC 6942091166600000

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

#define loop(it) for(auto it = mep.begin();it!=mep.end();++it)

using namespace std;

int main(){

    int n;

    cin>>n;

    vector<ll> arr(420);

	vector<ll> pref(420);

    vector<vector<ll>> dp(666,vector<ll>(420 , 0));

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

		cin>>arr[i];

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

	}

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

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

			int l = j , r = j+i;

			dp[l][r] = THICC;

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

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

			}

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

        }

	}

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

}

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

using namespace::std;



const int N = 400 + 5;

const long long inf = 1e18;



int n;

int a[N];

bool vis[N][N];

long long prefix[N];

long long memo[N][N];



long long getSize(int l, int r){

	if(r <= l) return 0LL;

	return l == 0? prefix[r] : prefix[r] - prefix[l-1];

}



long long DP(int l, int r){

	if(r <= l) return 0LL;

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

	if(vis[l][r]) return memo[l][r];

	long long ans = inf;

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

		long long cand = DP(l, k) + getSize(l, r) + DP(k + 1, r);

		if(ans > cand){

			ans = cand;

		}

	}

	vis[l][r] = true;

	return memo[l][r] = ans;

}



int main(){

	scanf("%d", &n);

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

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

		prefix[i] = a[i];

		if(i > 0) prefix[i] += prefix[i - 1];

	}

	printf("%lld\n", DP(0, n - 1));

	return 0;

}