Submission #708284

#	Time	Username	Problem	Language	Result	Execution time	Memory
708284		Cyanmond	Furniture (JOI20_furniture)	C++17	100 / 100	2902 ms	31596 KiB

furniture

#include <bits/stdc++.h>

constexpr int L = 1001, inf = 1001001001;
std::array<std::array<int, L>, L> dp, times;
std::vector<std::pair<int, int>> ps;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<bool>> C(N, std::vector<bool>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int x;
            std::cin >> x;
            C[i][j] = (x == 0);
            if (C[i][j]) {
                times[i][j] = inf;
            } else {
                times[i][j] = -1;
            }
        }
    }
    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];
        times[X[i]][Y[i]] = i;
    }

    std::stack<std::pair<std::pair<int, int>, std::pair<int, int>>> stk;
    ps.push_back({0, 0});
    ps.push_back({N - 1, M - 1});

    auto calc = [&](int l1, int r1, int l2, int r2) {
        for (int i = l1; i <= r1; ++i) {
            for (int j = l2; j <= r2; ++j) {
                dp[i][j] = -1;
            }
        }
        dp[l1][l2] = inf;
        for (int i = l1; i < r1; ++i) {
            for (int j = l2; j < r2; ++j) {
                const int m = std::min(dp[i][j], times[i][j + 1]);
                dp[i][j + 1] = std::max(dp[i][j + 1], m);
                const int m2 = std::min(dp[i][j], times[i + 1][j]);
                dp[i + 1][j] = std::max(dp[i + 1][j], m2);
            }
        }
        for (int i = l1; i < r1; ++i) {
            const int m = std::min(dp[i][r2], times[i + 1][r2]);
            dp[i + 1][r2] = std::max(dp[i + 1][r2], m);
        }
        for (int i = l2; i < r2; ++i) {
            const int m = std::min(dp[r1][i], times[r1][i + 1]);
            dp[r1][i + 1] = std::max(dp[r1][i + 1], m);
        }
    };

    stk.push({{0, N - 1}, {0, M - 1}});
    calc(0, N - 1, 0, M - 1);
    std::vector<int> answer(Q, 1);
    while (not stk.empty()) {
        const auto t = stk.top();
        stk.pop();
        const int lx = t.first.first, rx = t.first.second, ly = t.second.first, ry = t.second.second;
        if ((rx - lx == 1 and ly == ry) or (rx == lx and ry - 1 == ly)) continue;
        if (dp[rx][ry] == inf) continue;
        const int x = X[dp[rx][ry]], y = Y[dp[rx][ry]];
        times[x][y] = inf;
        answer[dp[rx][ry]] = 0;
        calc(x, rx, y, ry);
        stk.push({{lx, x}, {ly, y}});
        stk.push({{x, rx}, {y, ry}});

        dp[x][y] = -1;
        if (x != 0) {
            dp[x][y] = std::max(dp[x][y], dp[x - 1][y]);
        }
        if (y != 0) {
            dp[x][y] = std::max(dp[x][y], dp[x][y - 1]);
        }
    }
    for (const auto e : answer) {
        std::cout << e << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95