oj.uz

Submission #698663

# Submission time Handle Problem Language Result Execution time Memory
698663 2023-02-14T07:24:11 Z Cyanmond L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 479680 KB 
#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    i64 x;
    i64 y;
};

constexpr int N = 1 << 13;

int main() {
    i64 W, H;
    int K;
    std::cin >> W >> H >> K;
    std::vector<Point> points(K);
    std::map<i64, int> mEx;
    for (auto &[x, y] : points) {
        std::cin >> x >> y;
        --x;
        --y;
        mEx[y] |= 1 << x;
    }

    auto searchNext = [&](int s) {
        static std::array<std::vector<int>, N> g;
        static std::vector<int> seen(N);

        if (seen[s]) {
            return g[s];
        }
        seen[s] = true;

        auto dfs = [&](auto &&self, int t, int b) -> void {
            if (b >= W) {
                g[s].push_back(t);
                return;
            }
            if (s & (1 << b)) {
                self(self, t, b + 1);
            }
            if (b != 0) {
                if (not (t & (1 << (b - 1)))) {
                    int newT = t;
                    newT |= 1 << (b - 1);
                    newT |= 1 << b;
                    self(self, newT, b + 1);
                }
            }
            if (b != W - 1) {
                int newT = t;
                newT |= 1 << b;
                newT |= 1 << (b + 1);
                self(self, newT, b + 2);

                newT = t;
                if (not(s & (1 << (b + 1)))) {
                    newT = t;
                    newT |= 1 << b;
                    self(self, newT, b + 2);
                    newT = t;
                    newT |= 1 << (b + 1);
                    self(self, newT, b + 2);
                }
            }
        };
        dfs(dfs, 0, 0);
        return g[s];
    };

    std::vector dp(1 << W, false);
    dp[(1 << W) - 1] = true;
    for (int i = 0; i < H; ++i) {
        std::vector ndp(1 << W, false);
        for (int s = 0; s < (1 << W); ++s) {
            if (not dp[s]) {
                continue;
            }
            const int b = mEx[i];
            const auto g = searchNext(s);
            for (const auto t : g) {
                if ((t & b) != 0) {
                    continue;
                }
                ndp[t | b] = true;
            }
        }
        dp = std::move(ndp);
    }
    std::cout << (dp[(1 << W) - 1] ? "YES" : "NO") << std::endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2175 ms 32840 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 40 ms 1144 KB Output is correct
11 Correct 4368 ms 32828 KB Output is correct
12 Incorrect 282 ms 2900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 13328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8066 ms 479680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8021 ms 152552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8044 ms 13488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2175 ms 32840 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 40 ms 1144 KB Output is correct
11 Correct 4368 ms 32828 KB Output is correct
12 Incorrect 282 ms 2900 KB Output isn't correct
13 Halted 0 ms 0 KB -