oj.uz

답안 #708277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708277 2023-03-11T13:46:36 Z Cyanmond Furniture (JOI20_furniture) C++17
0 / 100
 1458 ms 524288 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], m);
            }
        }
        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 (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';
    }
}

Compilation message

furniture.cpp: In lambda function:
furniture.cpp:50:27: warning: unused variable 'm2' [-Wunused-variable]
   50 |                 const int m2 = std::min(dp[i][j], times[i + 1][j]);
      |                           ^~

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Runtime error 1458 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Runtime error 1458 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -