Submission #698679

#	Time	Username	Problem	Language	Result	Execution time	Memory
698679		Cyanmond	L-triominoes (CEOI21_ltriominoes)	C++17	10 / 100	8053 ms	524288 KiB

ltrominoes

#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);
                return;
            }
            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) {
                if (s & (1 << (b + 1))) {
                    int newT = t;
                    newT |= 1 << b;
                    newT |= 1 << (b + 1);
                    self(self, newT, b + 2);
                } else {
                    int 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: 10 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20