oj.uz

Submission #708284

# Submission time Handle Problem Language Result Execution time Memory
708284 2023-03-11T13:53:42 Z Cyanmond Furniture (JOI20_furniture) C++17
100 / 100
 2902 ms 31596 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1268 KB Output is correct
7 Correct 3 ms 1304 KB Output is correct
8 Correct 3 ms 1308 KB Output is correct
9 Correct 3 ms 1240 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1268 KB Output is correct
7 Correct 3 ms 1304 KB Output is correct
8 Correct 3 ms 1308 KB Output is correct
9 Correct 3 ms 1240 KB Output is correct
10 Correct 8 ms 1348 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 150 ms 14520 KB Output is correct
13 Correct 54 ms 9840 KB Output is correct
14 Correct 214 ms 26728 KB Output is correct
15 Correct 230 ms 27348 KB Output is correct
16 Correct 2902 ms 29556 KB Output is correct
17 Correct 298 ms 30784 KB Output is correct
18 Correct 613 ms 30156 KB Output is correct
19 Correct 290 ms 31596 KB Output is correct
20 Correct 249 ms 31560 KB Output is correct
21 Correct 260 ms 31544 KB Output is correct