Submission #10299697

---

Source Code Expand

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    const long long INF = 1LL<<60;
    long long lb = -INF, ub = INF;
    while (ub - lb > 1) {
        long long x = (ub + lb) / 2;
        int dp[2][n+1];
        dp[0][n] = dp[1][n] = 0;
        for (int i = n-1; i >= 0; i--) {
            long long s = 0;
            dp[0][i] = -n-1; dp[1][i] = n+1;
            for (int j = i; j < n; j++) {
                s += a[j];
                int d = s >= x ? 1 : -1;
                dp[0][i] = max(dp[0][i], dp[1][j+1] + d);
                dp[1][i] = min(dp[1][i], dp[0][j+1] + d);
            }
        }
        if (dp[0][0] >= 0) lb = x;
        else ub = x;
    }
    cout << lb << endl;
}

Submission Info

Judge Result