oj.uz

Submission #708260

# Submission time Handle Problem Language Result Execution time Memory
708260 2023-03-11T13:02:46 Z Cyanmond Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 6824 KB 
#include <bits/stdc++.h>

bool judge(const std::vector<std::vector<bool>> &fMap) {
    const int n = (int)fMap.size(), m = (int)fMap[0].size();
    std::vector<std::vector<bool>> dp(n, std::vector<bool>(m));
    if (not fMap[0][0]) return false;
    dp[0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (not dp[i][j]) continue;
            if (i != n - 1 and fMap[i + 1][j]) dp[i + 1][j] = true;
            if (j != m - 1 and fMap[i][j + 1]) dp[i][j + 1] = true;
        }
    }
    return dp[n - 1][m - 1];
}

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<bool>> C(N, std::vector<bool>(M));
    for (auto &vec : C) {
        for (int j = 0; j < M; ++j) {
            int x;
            std::cin >> x;
            vec[j] = (x == 0);
        }
    }
    int Q;
    std::cin >> Q;
    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }

    // answer
    for (int i = 0; i < Q; ++i) {
        C[X[i]][Y[i]] = false;
        if (not judge(C)) {
            C[X[i]][Y[i]] = true;
        }
        std::cout << (C[X[i]][Y[i]] ? 0 : 1) << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 118 ms 340 KB Output is correct
3 Correct 119 ms 360 KB Output is correct
4 Correct 248 ms 432 KB Output is correct
5 Correct 287 ms 460 KB Output is correct
6 Correct 364 ms 468 KB Output is correct
7 Correct 297 ms 460 KB Output is correct
8 Correct 330 ms 456 KB Output is correct
9 Correct 327 ms 468 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 118 ms 340 KB Output is correct
3 Correct 119 ms 360 KB Output is correct
4 Correct 248 ms 432 KB Output is correct
5 Correct 287 ms 460 KB Output is correct
6 Correct 364 ms 468 KB Output is correct
7 Correct 297 ms 460 KB Output is correct
8 Correct 330 ms 456 KB Output is correct
9 Correct 327 ms 468 KB Output is correct
10 Correct 3763 ms 1036 KB Output is correct
11 Correct 161 ms 340 KB Output is correct
12 Execution timed out 5056 ms 6824 KB Time limit exceeded
13 Halted 0 ms 0 KB -