stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

long long n,a[410],dp[410][410],pref[410];

long long f(long long l,long long r)

{

//	printf("%lld %lld\n",l,r);

	if(r<=l || l>=r) return 0;

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

	for(long long i=l;i<r;i++)

	{

	//	printf("c = %lld %lld %lld\n",i,i+1,a[i]+a[i+1]);

		if(dp[l][r]==-1)dp[l][r] = f(l,i)+f(i+1,r); 

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

	}

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

}

int main()

{

	scanf("%lld",&n);

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

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

	{

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

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

	}	

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

//	printf("c : \n");

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

//	{

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

//		{

//			printf("%d %d %lld\n",i,j,dp[i][j]);

//		}

//	}

	return 0;

}

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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 4e2+5;



const int mod = 1e9+7;



int n;

int ar[N];

long long prefix[N];

long long mem[N][N];



long long getsum(int l , int r){

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

}



long long go(int l , int r){

    if(r - l + 1 == 2)

        return getsum(l , r);

    if(l >= r)

        return 0;

    if(~mem[l][r])

        return mem[l][r];

    long long best = 1e18;

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

        best = min(best , go(l , i) + go(i + 1 , r) + getsum(l , i) + getsum(i + 1 , r));

    }

    return mem[l][r] = best;

}



int main(){

    scanf("%d" , &n);

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

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

        prefix[i] = ar[i] + prefix[i - 1];

    }

    memset(mem , -1 , sizeof mem);

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

}


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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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

using namespace std;

const int N = 2e4 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;

const long long OO = 1e18+25;

#define par pair<pair<int,int>, int>

#define f first

#define s second



int n, a[405];

long long mem[405][405],cum[405];



long long dp(int start=1, int end=n)

{

    if(start == end) return 0;

    long long &ret =mem[start][end];

    if(~ret) return ret;

    ret = OO;

    for(int i=start; i<end; i++)

    {

        ret = min(ret,1ll* dp(start, i)+dp(i+1, end)+(cum[i]-cum[start-1])+(cum[end]-cum[i]));

    }

    return ret;

}



int main()

{

    memset(mem, -1, sizeof mem);

    scanf("%d",&n);

    for(int i=1; i<=n ;i++)scanf("%d",a+i);

    for(int i=1; i<=n ;i++)cum[i] = cum[i-1]+a[i];

    printf("%lld",dp());

    return 0;

}

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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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

using namespace std;

#define endl '\n'

long long arr[401];

int n;

long long dp[401][401];

long long f(int l,int r){

	if(l==r)return 0;

	long long &mi=dp[l][r];

	if(~mi)return mi;

	mi=1000000000000000000LL;

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

		mi=min(mi,f(l,i)+f(i+1,r)+arr[r]-arr[l-1]);

	}

	return mi;

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	memset(dp,-1,sizeof dp);



	cin>>n;

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

		cin>>arr[i];

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

	}





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



	return 0;

}

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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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



using namespace std;



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

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

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

#define ll long long

#define pb					push_back

#define fIO ios_base::sync_with_stdio(0);cin.tie(0);



const ll oo = 1e8;

const double pi = 3.1415926535897;





const double EPS = (1e-7);

int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}





typedef vector<int>                vi;

typedef vector<pair<int,int>>      vii;

typedef vector<ll>                 vll;

typedef vector<double>             vd;

typedef vector< vi >               vvi;

typedef vector< vd >               vvd;

typedef vector<string>             vs;

typedef pair<int, int>             pii;



/**

    * PLEASEEE READDD PROBLEEEM CARFULLY ****

    * Always check for OVERFLOW ll vs int

    * Always check for array bounds

    * Check for function return

    * READ OUTPUT SECTION AGAIN!!!

**/



struct edge{

    int from, to, w;



    edge(){}

    edge(int x, int y, int we): from(x), to(y), w(we){}



    bool operator < (const edge &rhs) const{

        return w > rhs.w;

    }



};



const int N = 400 + 5;



ll dp[N][N];

ll pre[N];

int a[N];



ll sol(int l ,int r) {

    if(l == r) return 0;



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

    if(ret != -1) return ret;



    ret = 1e18L;

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

        ret = min(ret, sol(l, i) + sol(i + 1, r) + pre[r + 1] - pre[l]);

    }



    return ret;

}







int main(){

    fIO

//    freopen("", "r", stdin);

//    freopen("", "w", stdout);



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



    int n;

    cin >> n;



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



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



    cout << sol(0, n - 1) << "\n";

}














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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

}
// Slower C++ solution:


#include <iostream>

#include <climits>

#include <cstring>

#include <algorithm>



using namespace std;



#define SIZE 420

long long cost[SIZE][SIZE], a[SIZE];



long long minimalSum(int l, int r) {

    if (     l     >=  r) return 0;

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

    long long MIN = LLONG_MAX, sum = 0;

    for (int i = l; i <= r; i++) sum += a[i];

    for (int i = l; i <  r; i++) MIN = min(MIN, minimalSum(l  , i)

                                          +sum+ minimalSum(i+1, r));

    return cost[l][r] = MIN;

}



int main() {

    memset(cost, -1, sizeof cost);

    int N; cin >> N;

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

    cout << minimalSum(0, N-1) << endl;

    return 0;

}


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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

}
// Slower C++ solution:
// Author : Mohamed Sameh

#include <bits/stdc++.h>

#define pb push_back

#define f first

#define s second

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

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

#define SZ(a) (int)a.size()

#define Flush fflush(stdout);

typedef long long ll ;

using namespace std ;

int n;

const int N = 4e2+9;

int a[N];

ll dp[N][N];

ll pre[N];

ll solve(int l = 0, int r = n-1)

{

  if (l >= r)return 0;

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

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

  if (~ret)return ret;

  ret = 1e18;

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

  {

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

  }

  return ret;

}

void test ()

{

  memset(dp, -1, sizeof dp);

  cin >> n;

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

    cin >> a[i];

  pre[0] = a[0];

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

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

  cout << solve() <<"\n";

}

int main()

{

  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  test();

}


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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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

using namespace std;

typedef long long ll;

ll dp[405][405];

ll sum[405];

ll a[405];

int main(){

	int n;

	scanf("%d",&n);

	memset(dp,0,sizeof(dp));

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

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

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

	}

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

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

			int ends = i + j - 1;

			dp[j][ends] = 1e17;

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

				dp[j][ends]=min(dp[j][ends],dp[j][k] + dp[k + 1][ends] + sum[ends] - sum[j - 1]);//中间重复的部分用前缀和加上去，妙啊！

			}

		}

	}

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

	return 0;

}

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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<stack>

#include<set>

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 5e2 + 5;

const int inf = 0x3f3f3f3f;

const int inF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const db eps = 1e-8;

ll a[maxn] , dp[maxn][maxn][2];

int main(){

	int n;cin >> n;

	memset(dp, inf , sizeof dp);

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

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

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

			int k = j+i-1;

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

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

			}

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

		}

	}

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

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

		cout << endl;

	}*/

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

	return 0;

}

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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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



#define Fast cin.tie(0), ios::sync_with_stdio(0)

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

#define louisfghbvc int t; cin >> t; while(t--)

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

using namespace std;

typedef long long LL;

typedef pair<LL, LL> ii;

typedef vector<LL> vi;



template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }



void dbg_out() { cerr << "\n"; }

template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }



const int N = 405;

LL arr[N];

LL pre[N];

LL dp[N][N];





LL dfs(int l, int r){

    //dbg_out(l, r);

    if(l == r) return 0;

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

    LL res = pre[r+1] - pre[l];

    LL mn = 1e14;

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

        mn = min(mn, dfs(l, k) + dfs(k+1, r));

    }

    return dp[l][r] = res + mn;

}



void solve(){

    int n;

    cin >> n;

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

    pre[0] = 0;

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



    memset(dp, -1, sizeof dp);

    cout << dfs(0, n-1) << "\n";

}



int main()

{

    Fast;

    //louisfghbvc{

        solve();

    //}

    return 0;

}


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

#define mod 1000000007



using namespace std;

long long n,i,d,k;

long long dp[405][405];

long long s[405];

long long a[405];

long long sum(int l, int r)

{

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

}

int main()

{

    cin>>n;

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

        cin>>a[i];

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

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



    for(d=1;d<n;d++)

    {

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

        {

            dp[i][i+d]=1e18;

            for(k=i;k<i+d;k++)

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



            dp[i][i+d]+=sum(i, i+d);

        }

    }



    cout<<dp[1][n];

    return 0;

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



using namespace std;



typedef long long ll;



const int N = 405;

ll arr[N];

ll cost[N][N];

ll dp[N][N];



ll solve(int i, int j)

{

  if(i == j)

    return 0;

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

  if(~ans)

    return ans;

  ans = 1e18;

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

  {

    ans = min(ans, cost[i][z] + solve(i, z) + solve(z + 1, j) + cost[z + 1][j]);

  }

  return ans;

}



int main()

{

  int n;

  cin >> n;

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

    cin >> arr[i];

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

  {

    cost[i][i] = arr[i];

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

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

  }

  memset(dp, -1, sizeof dp);

  cout << solve(0, n - 1);

  return 0;

}


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



using namespace std;



typedef long long ll;



const int N = 405;

ll arr[N];

ll dp[N][N];

ll cost[N][N];



int main()

{

  int n;

  cin >> n;

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

    cin >> arr[i];

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

  {

    cost[i][i] = arr[i];

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

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

  }

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

  {

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

    {

      dp[i][j] = 1e18;

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

      {

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

      }

    }

  }

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

  return 0;

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

const int INF=1e9,MOD=1e9+7;

const long long LINF=1e18;

using namespace std;

#define int long long

//template

typedef pair<int,int> P;

P dp[402][402];

std::vector<int> v(500);

P f(int i,int j){

  if(dp[i][j]!=P(-1,-1))return dp[i][j];

  if(i==j)return P(v[i],v[i]);

  int res=LINF;

  for(int k=i;k<j;k++)res=min(res,f(i,k).first+f(k+1,j).first);

  return dp[i][j]=P(res+f(i,i).second+f(i+1,j).second,f(i,i).second+f(i+1,j).second);

}

//main

signed main(){

  int N;cin>>N;

  for(int i=0;i<N;i++)cin>>v[i];

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

  /*

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

    for(int j=0;j<N;j++)cout<<i<<" "<<j<<" "<<f(i,j).first<<endl;

  }

  */

  cout<<f(0,N-1).first-f(0,N-1).second<<endl;

}


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

using namespace std;



template<typename T>

void chmin(T &a,T b){

  if(a>b||!a)a=b;

}

using ll=long long;

ll dp[500][500],wa[500],v[500];

ll f(int l,int r){

  if(~dp[l][r])return dp[l][r];

  ll res=0;

  for(int i=l+1;i<r;i++)chmin(res,f(l,i)+f(i,r));

  return dp[l][r]=res+wa[r]-wa[l];

}



signed main(){

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

  int n;cin>>n;

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

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

  cout<<f(0,n)-wa[n]<<endl;

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

using namespace std;

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

typedef long long ll;

const int MAX = 401;

const ll INF = 1e17;



ll sum[MAX] = {};

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



ll dfs(int i, int j){

    if(dp[i][j] != -1) return dp[i][j];

    if(i == j) return dp[i][j] = 0;

    ll d = INF;

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

        d = min(d,dfs(i,k)+dfs(k+1,j)+sum[j]-sum[i-1]);

    }

    return dp[i][j] = d;

}





int main(){

    int n;

    cin >> n;

    rep(i,n){ 

        ll a;

        cin >> a;

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

    }

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

    return 0;

}

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

using namespace std;

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

using ll = long long;

const ll INF = 1e17;



int main(){

  int n;

  cin >> n;

  ll a[n];

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

  vector<vector<ll>> dp(n,vector<ll>(n,INF));

  vector<ll> sum(n+1);

  rep(i,n) {

    dp[i][i] = 0;

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

  }

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

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

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

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

      }

    }

  }

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

  return 0;

}
// Slower C++ solution:
/*********************

*  Author: xuziyuan  * 

*********************/



#include <bits/stdc++.h>



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

#define repn(i,n) for(int i=1;i<=n;i++)

#define LL long long

#define pii pair <int,int>

#define fi first

#define se second

#define pb push_back

#define mpr make_pair



using namespace std;



const LL MOD=1e9+7;



LL n,x,sum[410],dp[410][410];



LL dfs(int lb,int ub)

{

  if(dp[lb][ub]!=-1) return dp[lb][ub];

  if(lb==ub) return dp[lb][ub]=0;

  dp[lb][ub]=1e18;

  for(int i=lb;i<ub;i++) dp[lb][ub]=min(dp[lb][ub],dfs(lb,i)+dfs(i+1,ub)+sum[ub+1]-sum[lb]);

  return dp[lb][ub];

}



int main()

{

  cin>>n;

  repn(i,n)

  {

    cin>>x;

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

  }

  rep(i,405) rep(j,405) dp[i][j]=-1;

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

  return 0;

}

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



#define LL long long



using namespace std;



LL n,a[410],dp[410][410],sum[410];



int main()

{

  cin>>n;

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

  {

	cin>>a[i];

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

  }

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

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

    {

      if(i+len-1>=n) break;

      int j=i+len-1;

      dp[i][j]=1e18;

      for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]);

    }

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

  return 0;

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

#define ll long long

const int N=5e5+10,mod=998244353;

int n,m,ans,fc[N],fi[N];

int main(){

	std::cin>>n>>m,fc[0]=fc[1]=fi[0]=fi[1]=1;

	for(int i=2;i<=m;i++)fc[i]=(ll)fc[i-1]*i%mod;

	for(int i=2;i<=m;i++)fi[i]=(ll)(mod-mod/i)*fi[mod%i]%mod;

	for(int i=2;i<=m;i++)fi[i]=(ll)fi[i-1]*fi[i]%mod;

	for(int i=n;i<=m;i++)ans=(ans+(ll)fc[m-1]*fi[i-1]%mod*fi[m-i])%mod;

	std::cout<<ans;

}

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



typedef long long LL;

const int Mod = 998244353;



inline int qPow(int b, int e) {

	int a = 1;

	for (; e; e >>= 1, b = (LL)b * b % Mod)

		if (e & 1) a = (LL)a * b % Mod;

	return a;

}



const int MN = 500005;



int Fac[MN], iFac[MN];



inline void Init(int N) {

	Fac[0] = 1;

	for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;

	iFac[N] = qPow(Fac[N], Mod - 2);

	for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;

}

inline int Binom(int N, int M) {

	if (M < 0 || M > N) return 0;

	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;

}



int N, K, Ans;



int main() {

	scanf("%d%d", &N, &K);

	if (K < N) return puts("0"), 0;

	Init(K);

	for (int R = 0; R <= K; ++R) {

		int B = K - R;

		if (R < B) continue;

		if (R == B) --B;

		Ans = ((LL)Ans + Binom(R + B, R) - Binom(R + B, 2 * R - N + 1) + Mod) % Mod;

	}

	printf("%d\n", Ans);

	return 0;

}



// Luogu : PinkRabbit