Submission #698684

#	Time	Username	Problem	Language	Result	Execution time	Memory
698684		Cyanmond	L-triominoes (CEOI21_ltriominoes)	C++17	7 / 100	1 ms	300 KiB

ltrominoes

#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    i64 x;
    i64 y;
};

constexpr int N = 1 << 16;

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

        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 auto g = searchNext(s);
            for (const auto t : g) {
                ndp[t] = true;
            }
        }
        dp = std::move(ndp);
    }
    return dp[(1 << W) - 1];
}

void exp() {
    int N = 16;
    for (int i = 2; i < N; ++i) {
        for (int j = 2; j < N; ++j) {
            if (judge(i, j)) {
                std::cout << i << ' ' << j << std::endl;
            }
        }
    }
}

void solve() {
    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;
    }

    if (H * W % 6 == 0 or (std::min(H, W) >= 5 and H * W % 3 == 0)) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}

int main() {
    solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 7 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20