Submission #5739350

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
using namespace std;

constexpr int MAX_N = 2000;
int solve(int n, const vector<bitset<MAX_N> > & wins) {
    vector<bitset<MAX_N> > dpl(n);
    vector<bitset<MAX_N> > dpr(n);
    REP_R (l, n) REP3 (r, l, n) {
        if (l == r) {
            dpl[r][l] = true;
            dpr[l][r] = true;
        } else {
            dpl[r][l] = (wins[l] & dpr[l + 1] & dpl[r]).any();
            dpr[l][r] = (wins[r] & dpr[l] & dpl[r - 1]).any();
        }
    }
    return (dpr[0] & dpl[n - 1]).count();
}

int main() {
    int n; cin >> n;
    assert (n <= MAX_N);
    vector<bitset<MAX_N> > wins(n);
    REP (i, n) {
        REP (j, i) {
            char c; cin >> c;
            wins[i][j] = c - '0';
            wins[j][i] = not wins[i][j];
        }
    }
    cout << solve(n, wins) << endl;
    return 0;
}

Submission Info

Judge Result