Submission #3664895

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;
using ll = long long;
static const ll INF = 1000000000000000ll;
static int dp[1001][2];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	ll lo = -INF, hi = INF;
	while(lo < hi){
		const ll mid = lo + (hi - lo) / 2;
		vector<array<int, 2>> dp(n + 1, {0, 0});
		for(int i = n - 1; i >= 0; --i){
			ll sum = 0;
			int alice = -n, bob = n;
			for(int j = i + 1; j <= n; ++j){
				sum += a[j - 1];
				if(sum >= mid){
					alice = max(alice, dp[j][1] + 1);
					bob   = min(bob,   dp[j][0] + 1);
				}else{
					alice = max(alice, dp[j][1] - 1);
					bob   = min(bob,   dp[j][0] - 1);
				}
			}
			dp[i][0] = alice;
			dp[i][1] = bob;
		}
		if(dp[0][0] >= 0){
			lo = mid + 1;
		}else{
			hi = mid;
		}
	}
	cout << lo - 1 << endl;
	return 0;
}

Submission Info

Judge Result