Submission #3665441

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;


int n;
vector<long long> a;
vector<vector<int>> memo;

int dfs(int ai, int p, long long th) {
    if (ai == n) return 0;
    if (memo[ai][p] != -M) return memo[ai][p];
    int ret;
    long long sum = 0;
    if (p == 0) {
        ret = -M;
        for (int i = ai; i < n; ++i) {
            sum += a[i];
            ret = max(ret, dfs(i + 1, !p, th) + (sum >= th ? 1 : -1));
        }
    }
    else {
        ret = M;
        for (int i = ai; i < n; ++i) {
            sum += a[i];
            ret = min(ret, dfs(i + 1, !p, th) + (sum >= th ? 1 : -1));
        }
    }
    return memo[ai][p] = ret;
}


int main() {
    cin >> n;
    a = vector<long long>(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    long long ok = -1e13, ng = 1e13;
    while (ok < ng - 1) {
        long long m = (ok + ng) / 2;
        memo = vector<vector<int>>(n, vector<int>(2, -M));
        if (dfs(0, 0, m) >= 0) {
            ok = m;
        }
        else {
            ng = m;
        }
    }
    cout << ok << "\n";
    return 0;
}

Submission Info

Judge Result