H - Median Game CODE THANKS FESTIVAL 2018(Parallel)

H - Median Game

解法
中央値は二分探索
いつものDPで後ろから解けば解ける

vi A, B, C;
int dpa[1001];//+
int dpb[1001];//sum以上 - sum 以下を最小で何個に
vi rui;
bool calc(int v) {
    fill(dpa, -LINF);
    fill(dpb, LINF);
    dpa[N] = dpb[N] = 0;
    for (int i = N - 1; i >= 0; --i) {
        rep(k, 1, N - i + 1) {
            int sum = rui[i + k] - rui[i];
            chmax(dpa[i], dpb[i + k] + (sum >= v ? 1 : -1));
            chmin(dpb[i], dpa[i + k] + (sum >= v ? 1 : -1));
        }
    }
    return dpa[0] >= 0;
}

signed main() {
    cin >> N;
    addAll(A, N);
    int ok = -LINF, ng = LINF;
    rui = ruiv(A);
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (calc(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;

    return 0;
}