stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//#pragma GCC target ("avx2,sse2")

//#pragma GCC optimization ("Ofast")

//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree <pair <ll, int>, null_type, less <pair <ll, int> >, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long

#define ull unsigned long long

#define db double

#define pb push_back

#define pf push_front

#define ppb pop_back

#define ppf pop_front

#define fi first

#define se second

#define mp make_pair

#define up_b upper_bound

#define low_b lower_bound

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

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

#define endl "\n"



#define left fsdsdfoisf

#define sum dpsdfioppsf

#define assign xcvjlkdjfio

#define trie fksdfkjkfnjuiv

#define next sidlfjsfkl

#define merge sdfksdkfsldf



#define int long long



using namespace std;



void dout() {

    cerr << endl;

}

template <typename Head, typename... Tail>

void dout(Head H, Tail... T) {

    cerr << H << ' ';

    dout(T...);

}



//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair <int, int> pii;



const int N = 407, inf = 1e15;

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



int calc(int l, int r) {

    if (l >= r) {

        return 0;

    }

    int & res = dp[l][r];

    if (res != -1) {

        return res;

    }

    res = inf;

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

        res = min(res, calc(l, i) + calc(i + 1, r) + (p[i] - p[l - 1]) + (p[r] - p[i]));

    }

    return res;

}



void solve(int tc) {

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

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

    cin >> n;

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

        cin >> a[i];

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

    }

    cout << calc(1, n);

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

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

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

    int tc = 1;

//    cin >> tc;

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

        solve(i);

//        cleanup();

    }

}


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

using namespace std;

const int N = 405;

int n, a[N];

long long sum[N], mem[N][N];

bool vis[N][N];



long long dp(int i, int j) {

	if (i == j) {

		return 0;

	}

	if (vis[i][j]) {

		return mem[i][j];

	}

	vis[i][j] = true;



	long long ans = LLONG_MAX;

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

		ans = min(ans, dp(i, m) + dp(m + 1, j));

	}



	long long cost = sum[j] - sum[i - 1];

	return mem[i][j] = cost + ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dp(1, n) << '\n';



	return 0;

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



using namespace std;



// Header files, namespaces,

// macros as defined above

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>





#define f first

#define s second

#define db long double

#define pb push_back

#define sz(c) (c).size()

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



typedef long long ll;

typedef pair <int , int> ii;

typedef pair <ii , int> iii;

typedef vector <int> vi;

typedef vector <ii> vii;

typedef vector <iii> viii;

typedef vector <vi> vvi;

typedef vector <vii> vvii;



const ll mod = 1e9+7;

const int MAX = 4e2+5;

const db eps = 1e-13;



ll memo[MAX][MAX] , v[MAX];





ll dp ( int lo , int hi ) {



    if( hi==lo )

        return 0;



    ll &res = memo[lo][hi];



    if( res != -1 )

        return res;



    res = 1e18;



    for( int i = lo ; i < hi ; i++ ) {



        res = min( ( dp( lo , i ) + dp( i+1 , hi ) ) + (v[i] - v[lo-1]) + (v[hi] - v[i]) , res );



    }



    return res;

}



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

    cout<<setprecision(11)<<fixed;

    memset( memo , -1 , sizeof memo );

    int n;cin>>n;

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

        cin>>v[i];

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



    }



    cout<<dp( 1, n )<<"\n";



}


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

using namespace std;

const int N = 405;

int n, a[N];

long long sum[N], mem[N][N];

bool vis[N][N];



long long dp(int i, int j) {

	if (i == j) {

		return 0;

	}

	if (vis[i][j]) {

		return mem[i][j];

	}

	vis[i][j] = true;



	long long ans = LLONG_MAX;

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

		ans = min(ans, dp(i, m) + dp(m + 1, j));

	}



	long long cost = sum[j] - sum[i - 1];

	return mem[i][j] = cost + ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n;

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

		cin >> a[i];

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

	}



	cout << dp(1, n) << '\n';



	return 0;

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

 

#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define forev(i, b, a) for(int i = (b); i >= (a); --i)

#define forn(i, a, b) for(int i = (a); i <= (b); ++i)

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

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

#define pb push_back

#define ppb pop_back

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb;  

typedef long long ll;  

typedef double db;                      

 

 

const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;

const pii base = {1171, 3307}, Mod = {1e9 + 7, 1e9 + 9};

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, a[N], dp[N][N];



int get (int l, int r) {

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

}



int rec (int l, int r) {

	if (r == l)	

		return 0;

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

		return dp[l][r];



	dp[l][r] = INF;



	forn (L, l, r - 1) 

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



	return dp[l][r];	

}





main () {

	cin >> n;

	forn (i, 1, n) {

		cin >> a[i]; 

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

	}



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

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

}



    

// Faster C++ solution for the same problem (measured speedup: 2.3286988234696384x):
/*input

3

1000000000 1000000000 1000000000

*/

#include<bits/stdc++.h>

#define fn(i,n) for(long long i=0;i<n;i++)

#define fn1(i,n) for(long long  i=1;i<=n;i++)

#define ll long long int

#define mp(x,y) make_pair(x,y)

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

ll n;cin>>n;

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

fn(i,n){cin>>a[i];dp[i][i]=0;}

fn(i,n-1)

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

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

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

{

	for(int k=0;k+l<n;k++)

	{

		if(k>0)

		dp[k][k+l]=a[k+l]-a[k-1];

		else

		dp[k][k+l]=a[k+l];

		ll p=1e18;

		fn(j,l)

		{

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

		}

		dp[k][k+l]+=p;

	}

}

//fn(i,n)

//cout<<a[i]<<" ";

/*

fn(i,n)

{

	fn(j,n)

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

	cout<<endl;

}*/

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

}
// Slower C++ solution:
//#pragma GCC target ("avx2,sse2")

//#pragma GCC optimization ("Ofast")

//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree <pair <ll, int>, null_type, less <pair <ll, int> >, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long

#define ull unsigned long long

#define db double

#define pb push_back

#define pf push_front

#define ppb pop_back

#define ppf pop_front

#define fi first

#define se second

#define mp make_pair

#define up_b upper_bound

#define low_b lower_bound

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

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

#define endl "\n"



#define left fsdsdfoisf

#define sum dpsdfioppsf

#define assign xcvjlkdjfio

#define trie fksdfkjkfnjuiv

#define next sidlfjsfkl

#define merge sdfksdkfsldf



#define int long long



using namespace std;



void dout() {

    cerr << endl;

}

template <typename Head, typename... Tail>

void dout(Head H, Tail... T) {

    cerr << H << ' ';

    dout(T...);

}



//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair <int, int> pii;



const int N = 407, inf = 1e15;

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



int calc(int l, int r) {

    if (l >= r) {

        return 0;

    }

    int & res = dp[l][r];

    if (res != -1) {

        return res;

    }

    res = inf;

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

        res = min(res, calc(l, i) + calc(i + 1, r) + (p[i] - p[l - 1]) + (p[r] - p[i]));

    }

    return res;

}



void solve(int tc) {

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

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

    cin >> n;

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

        cin >> a[i];

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

    }

    cout << calc(1, n);

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

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

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

    int tc = 1;

//    cin >> tc;

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

        solve(i);

//        cleanup();

    }

}


// Faster C++ solution for the same problem (measured speedup: 2.3243854162575626x):
/*input

3

1000000000 1000000000 1000000000

*/

#include<bits/stdc++.h>

#define fn(i,n) for(long long i=0;i<n;i++)

#define fn1(i,n) for(long long  i=1;i<=n;i++)

#define ll long long int

#define mp(x,y) make_pair(x,y)

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

ll n;cin>>n;

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

fn(i,n){cin>>a[i];dp[i][i]=0;}

fn(i,n-1)

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

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

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

{

	for(int k=0;k+l<n;k++)

	{

		if(k>0)

		dp[k][k+l]=a[k+l]-a[k-1];

		else

		dp[k][k+l]=a[k+l];

		ll p=1e18;

		fn(j,l)

		{

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

		}

		dp[k][k+l]+=p;

	}

}

//fn(i,n)

//cout<<a[i]<<" ";

/*

fn(i,n)

{

	fn(j,n)

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

	cout<<endl;

}*/

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

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



using namespace std;



// Header files, namespaces,

// macros as defined above

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>





#define f first

#define s second

#define db long double

#define pb push_back

#define sz(c) (c).size()

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



typedef long long ll;

typedef pair <int , int> ii;

typedef pair <ii , int> iii;

typedef vector <int> vi;

typedef vector <ii> vii;

typedef vector <iii> viii;

typedef vector <vi> vvi;

typedef vector <vii> vvii;



const ll mod = 1e9+7;

const int MAX = 4e2+5;

const db eps = 1e-13;



ll memo[MAX][MAX] , v[MAX];





ll dp ( int lo , int hi ) {



    if( hi==lo )

        return 0;



    ll &res = memo[lo][hi];



    if( res != -1 )

        return res;



    res = 1e18;



    for( int i = lo ; i < hi ; i++ ) {



        res = min( ( dp( lo , i ) + dp( i+1 , hi ) ) + (v[i] - v[lo-1]) + (v[hi] - v[i]) , res );



    }



    return res;

}



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

    cout<<setprecision(11)<<fixed;

    memset( memo , -1 , sizeof memo );

    int n;cin>>n;

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

        cin>>v[i];

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



    }



    cout<<dp( 1, n )<<"\n";



}


// Faster C++ solution for the same problem (measured speedup: 2.314321169236108x):
/*input

3

1000000000 1000000000 1000000000

*/

#include<bits/stdc++.h>

#define fn(i,n) for(long long i=0;i<n;i++)

#define fn1(i,n) for(long long  i=1;i<=n;i++)

#define ll long long int

#define mp(x,y) make_pair(x,y)

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

ll n;cin>>n;

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

fn(i,n){cin>>a[i];dp[i][i]=0;}

fn(i,n-1)

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

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

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

{

	for(int k=0;k+l<n;k++)

	{

		if(k>0)

		dp[k][k+l]=a[k+l]-a[k-1];

		else

		dp[k][k+l]=a[k+l];

		ll p=1e18;

		fn(j,l)

		{

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

		}

		dp[k][k+l]+=p;

	}

}

//fn(i,n)

//cout<<a[i]<<" ";

/*

fn(i,n)

{

	fn(j,n)

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

	cout<<endl;

}*/

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

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

using namespace std;



long long int dp[404][404];

int n;

long long int a[404];



long long int fn(int i, int j) {

    if (i == j) return 0;

    if (~dp[i][j]) return dp[i][j];

    dp[i][j] = LLONG_MAX;

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

        dp[i][j] = min(dp[i][j], fn(i, k) + fn(k + 1, j) + (a[j] - (i > 0? a[i - 1] : 0))); 

    }

    return dp[i][j];

}



int main() {

    scanf("%d", &n);

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

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

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

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

    }

    memset(dp, -1, sizeof dp);

    cout << fn(0, n - 1) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.284481568178763x):
/*input

3

1000000000 1000000000 1000000000

*/

#include<bits/stdc++.h>

#define fn(i,n) for(long long i=0;i<n;i++)

#define fn1(i,n) for(long long  i=1;i<=n;i++)

#define ll long long int

#define mp(x,y) make_pair(x,y)

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

ll n;cin>>n;

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

fn(i,n){cin>>a[i];dp[i][i]=0;}

fn(i,n-1)

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

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

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

{

	for(int k=0;k+l<n;k++)

	{

		if(k>0)

		dp[k][k+l]=a[k+l]-a[k-1];

		else

		dp[k][k+l]=a[k+l];

		ll p=1e18;

		fn(j,l)

		{

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

		}

		dp[k][k+l]+=p;

	}

}

//fn(i,n)

//cout<<a[i]<<" ";

/*

fn(i,n)

{

	fn(j,n)

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

	cout<<endl;

}*/

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

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

 

#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define forev(i, b, a) for(int i = (b); i >= (a); --i)

#define forn(i, a, b) for(int i = (a); i <= (b); ++i)

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

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

#define pb push_back

#define ppb pop_back

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb;  

typedef long long ll;  

typedef double db;                      

 

 

const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 411;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;

const pii base = {1171, 3307}, Mod = {1e9 + 7, 1e9 + 9};

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, a[N], dp[N][N];



int get (int l, int r) {

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

}



int rec (int l, int r) {

	if (r == l)	

		return 0;

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

		return dp[l][r];



	dp[l][r] = INF;



	forn (L, l, r - 1) 

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



	return dp[l][r];	

}





main () {

	cin >> n;

	forn (i, 1, n) {

		cin >> a[i]; 

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

	}



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

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

}



    

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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



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

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

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



using namespace std;



// Header files, namespaces,

// macros as defined above

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>





#define f first

#define s second

#define db long double

#define pb push_back

#define sz(c) (c).size()

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



typedef long long ll;

typedef pair <int , int> ii;

typedef pair <ii , int> iii;

typedef vector <int> vi;

typedef vector <ii> vii;

typedef vector <iii> viii;

typedef vector <vi> vvi;

typedef vector <vii> vvii;



const ll mod = 1e9+7;

const int MAX = 4e2+5;

const db eps = 1e-13;



ll memo[MAX][MAX] , v[MAX];





ll dp ( int lo , int hi ) {



    if( hi==lo )

        return 0;



    ll &res = memo[lo][hi];



    if( res != -1 )

        return res;



    res = 1e18;



    for( int i = lo ; i < hi ; i++ ) {



        res = min( ( dp( lo , i ) + dp( i+1 , hi ) ) + (v[i] - v[lo-1]) + (v[hi] - v[i]) , res );



    }



    return res;

}



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

    cout<<setprecision(11)<<fixed;

    memset( memo , -1 , sizeof memo );

    int n;cin>>n;

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

        cin>>v[i];

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



    }



    cout<<dp( 1, n )<<"\n";



}


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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



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

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

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

using namespace std;



long long int dp[404][404];

int n;

long long int a[404];



long long int fn(int i, int j) {

    if (i == j) return 0;

    if (~dp[i][j]) return dp[i][j];

    dp[i][j] = LLONG_MAX;

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

        dp[i][j] = min(dp[i][j], fn(i, k) + fn(k + 1, j) + (a[j] - (i > 0? a[i - 1] : 0))); 

    }

    return dp[i][j];

}



int main() {

    scanf("%d", &n);

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

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

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

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

    }

    memset(dp, -1, sizeof dp);

    cout << fn(0, n - 1) << endl;

    return 0;

}

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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



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

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef double dd;

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

#define endl "\n"

#define clr (n, r) memset(n,r,sizeof(n));



void fast() {

    cin.tie(0);

    cin.sync_with_stdio(0);

}



const ll MAX = 405;

ll n, arr[MAX], dp[MAX][MAX], pre[MAX];



ll ans(ll i = 0, ll j = n-1) {

    ll &ret=dp[i][j];

    if(~ret)return ret;

    if(i<0||j<0||i==n||j==n)return 0;

    if (i == j)return arr[i];

    if (i > j)return 0;

    ll solu = 1e15;

    ll res = 0;

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

        res = ans(i, k) + ans(k + 1, j) + pre[j + 1] - pre[i];

       // cout<<i<<" "<<j<<endl;

        solu = min(solu, res);

    }

    return ret=solu;

}



int main() {

    fast();

    cin >> n;

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

        cin >> arr[i];

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

    }

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

    cout << ans()-pre[n];

}

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

#include <bits/stdc++.h>

using namespace std;



typedef vector<int> vi;

#define ll long long

#define PI 3.14159265359

#define x first

#define y second

#define point pair<int,int>

#define clr(x, val)	memset((x), (val), sizeof(x))



//you don't know math, unless you can do math!

ll dp[400][400];

ll OO = 1e15 + 10;



vector<ll> a, a_sum;

int main() {

    int n; cin>>n;

    a= vector<ll> (n);

    a_sum = vector<ll> (n);



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

        cin>>a[i];

        a_sum[i] = a[i];

        if(i) a_sum[i]+= a_sum[i - 1];

    }





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

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

    }



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

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

         int j = i + sz;

         dp[i][j] = OO;



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

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



         dp[i][j] += a_sum[j];

         if(i - 1 >= 0) dp[i][j] -= a_sum[i - 1];

        }

    }



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

}