stablegradients/pie-gem5-pairs huggingface dataset:
// 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: 1.1104391280117705x):
#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));

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

#define fast ios::sync_with_stdio(0);cin.tie(0);

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



	printf("%lld\n", dp[0][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.331539075903178x):
#include<bits/stdc++.h>

#define fast ios::sync_with_stdio(0);cin.tie(0);

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



	printf("%lld\n", dp[0][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.4480096169031413x):
#include<bits/stdc++.h>

#define fast ios::sync_with_stdio(0);cin.tie(0);

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



	printf("%lld\n", dp[0][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.3950541132530865x):
#include<bits/stdc++.h>

#define fast ios::sync_with_stdio(0);cin.tie(0);

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



	printf("%lld\n", dp[0][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.0573977695939942x):
#include<bits/stdc++.h>

#define fast ios::sync_with_stdio(0);cin.tie(0);

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;



const int M = 400;

int n, a[M];

ll ps[M + 1], dp[M + 2][M + 2];



int main()

{

	scanf("%d", &n);

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

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

	}

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

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

	}

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

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

			dp[i][j] = LLONG_MAX;

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

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

			}

		}

	}



	printf("%lld\n", dp[0][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.338060185247532x):
#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];

	}

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

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

			int j = len + i;

			if(j > n) break;

			ll res = 1e17;

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

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

			}

			dp[i][j] = res + pre[j] - pre[i-1];

		}

	}

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

	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.2989312771432204x):
#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];

	}

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

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

			int j = len + i;

			if(j > n) break;

			ll res = 1e17;

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

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

			}

			dp[i][j] = res + pre[j] - pre[i-1];

		}

	}

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

	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.4137729164440263x):
#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];

	}

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

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

			int j = len + i;

			if(j > n) break;

			ll res = 1e17;

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

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

			}

			dp[i][j] = res + pre[j] - pre[i-1];

		}

	}

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

	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.3475724980194927x):
#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];

	}

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

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

			int j = len + i;

			if(j > n) break;

			ll res = 1e17;

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

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

			}

			dp[i][j] = res + pre[j] - pre[i-1];

		}

	}

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

	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.0146384557011117x):
#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];

	}

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

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

			int j = len + i;

			if(j > n) break;

			ll res = 1e17;

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

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

			}

			dp[i][j] = res + pre[j] - pre[i-1];

		}

	}

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

	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.311487244129113x):
#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>

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.2728030509118025x):
#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;

}