Submission #2270962

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define gt first
#define gc second.first
#define gr second.second
#define MOD (1000000007ll)
#define l_ength size
#define PI 3.14159265358979

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll a[575],d[575][575];

ll dist(int l, int r){
	int i;
	ll sm=0ll,mx=0ll;
	if(l == r){
		return 0ll;
	}
	if(l > r){
		swap(l,r);
	}
	for(i=l; i<r; ++i){
		sm += a[i];
		mx = max(mx,a[i]);
	}
	return max(mx*2-sm,0ll);
}

int main(void){
	int n,i,j,k;
	ll sum=0ll;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i];
		sum += a[i];
	}
	cout << sum << endl;
	for(i=0; i<=n; ++i){
		for(j=0; j<=n; ++j){
			d[i][j] = dist(i,j);
		}
	}
	for(k=0; k<=n; ++k){
		for(i=0; i<=n; ++i){
			for(j=0; j<=n; ++j){
				d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	cout << d[0][n] << endl;
}

Submission Info

Judge Result