Submission #5739350


Source Code Expand

Copy
#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

Submission Time
Task F - Random Tournament
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1014 Byte
Status
Exec Time 517 ms
Memory 1792 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 1000 / 1000 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 11 ms 512 KB
001.txt 11 ms 512 KB
002.txt 11 ms 512 KB
003.txt 11 ms 512 KB
004.txt 11 ms 512 KB
005.txt 12 ms 512 KB
006.txt 12 ms 512 KB
007.txt 13 ms 512 KB
008.txt 13 ms 512 KB
009.txt 13 ms 512 KB
010.txt 13 ms 512 KB
011.txt 13 ms 512 KB
012.txt 13 ms 512 KB
013.txt 13 ms 512 KB
014.txt 13 ms 512 KB
015.txt 12 ms 512 KB
016.txt 13 ms 512 KB
017.txt 12 ms 512 KB
018.txt 13 ms 512 KB
019.txt 13 ms 512 KB
020.txt 13 ms 512 KB
021.txt 13 ms 512 KB
022.txt 13 ms 512 KB
023.txt 13 ms 512 KB
024.txt 13 ms 512 KB
025.txt 13 ms 512 KB
026.txt 13 ms 512 KB
027.txt 13 ms 512 KB
028.txt 13 ms 512 KB
029.txt 13 ms 512 KB
030.txt 13 ms 512 KB
031.txt 13 ms 512 KB
032.txt 13 ms 512 KB
033.txt 12 ms 512 KB
034.txt 12 ms 512 KB
035.txt 13 ms 512 KB
036.txt 13 ms 512 KB
037.txt 13 ms 512 KB
038.txt 13 ms 512 KB
039.txt 13 ms 512 KB
040.txt 13 ms 512 KB
041.txt 13 ms 512 KB
042.txt 13 ms 512 KB
043.txt 13 ms 512 KB
044.txt 13 ms 512 KB
045.txt 13 ms 512 KB
046.txt 13 ms 512 KB
047.txt 12 ms 512 KB
048.txt 12 ms 512 KB
049.txt 12 ms 512 KB
050.txt 466 ms 1792 KB
051.txt 491 ms 1792 KB
052.txt 510 ms 1792 KB
053.txt 499 ms 1792 KB
054.txt 493 ms 1792 KB
055.txt 497 ms 1792 KB
056.txt 500 ms 1792 KB
057.txt 489 ms 1792 KB
058.txt 501 ms 1792 KB
059.txt 496 ms 1792 KB
060.txt 496 ms 1792 KB
061.txt 500 ms 1792 KB
062.txt 514 ms 1792 KB
063.txt 517 ms 1792 KB
064.txt 515 ms 1792 KB
065.txt 512 ms 1792 KB
066.txt 510 ms 1792 KB
067.txt 493 ms 1792 KB
068.txt 514 ms 1792 KB
069.txt 511 ms 1792 KB
070.txt 494 ms 1792 KB
071.txt 489 ms 1792 KB
072.txt 482 ms 1792 KB
073.txt 496 ms 1792 KB
example0.txt 1 ms 256 KB
example1.txt 1 ms 256 KB