Submission #708260

#	Time	Username	Problem	Language	Result	Execution time	Memory
708260		Cyanmond	Furniture (JOI20_furniture)	C++17	5 / 100	5056 ms	6824 KiB

furniture

#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 / 5
• Subtask 2: 0 / 95