Submission #1125167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125167		Pannda	L-triominoes (CEOI21_ltriominoes)	C++20	10 / 100	7015 ms	1432 KiB

ltrominoes

#include <bits/stdc++.h>
using namespace std;

void subtask1(int w, int h, int k, vector<array<int, 2>> tiled) {
    vector<vector<int>> a(h + 1, vector<int>(w, 0));
    for (auto [x, y] : tiled) {
        a[x][y] = 1;
    }
    for (int j = 0; j < w; j++) {
        a[h][j] = 1;
    }

    auto get = [&](int mask, int i) -> int {
        return mask >> i & 1;
    };

    vector<vector<int>> prev(1 << w, vector<int>(2, 0));
    {
        int mask = 0;
        for (int i = 0; i < w; i++) {
            if (a[0][i]) mask |= 1 << i;
        }
        prev[mask][a[1][0]] = 1;
    }

    for (int i = 0; i + 1 < h; i++) {
        for (int j = 0; j < w; j++) {
            vector<vector<int>> dp(1 << w, vector<int>(2, 0));
            for (int mask = 0; mask < (1 << w); mask++) {
                if (get(mask, j)) {
                    int c = j + 1 < w ? a[i + 1][j + 1] : a[i + 2][0];
                    dp[mask - (1 << j)][c] |= prev[mask][0];
                    dp[mask][c] |= prev[mask][1];
                } else {
                    int c = j + 1 < w ? a[i + 1][j + 1] : a[i + 2][0];

                    if (j > 0 && !get(mask, j - 1))
                        dp[mask + (3 << (j - 1))][c] |= prev[mask][0];
                    if (j + 1 < w && !a[i + 1][j + 1])
                        dp[mask + (1 << j)][1] |= prev[mask][0];
                    if (j + 1 < w && !get(mask, j + 1))
                        dp[mask + (3 << j)][c] |= prev[mask][0];
                    if (j + 1 < w && !get(mask, j + 1) && !a[i + 1][j + 1])
                        dp[mask + (2 << j)][1] |= prev[mask][0];

                    if (j + 1 < w && !get(mask, j + 1) && !a[i + 1][j + 1])
                        dp[mask + (3 << j)][1] |= prev[mask][1];
                }
            }
            prev = dp;
        }
    }
    prev[(1 << w) - 1][1] ? cout << "YES\n" : cout << "NO\n";
    exit(0);
}

void subtask2(int w, int h, int k, vector<array<int, 2>> tiled) {
    bool ok = false;
    if (w % 2 == 0 && h % 3 == 0) ok = true;
    if (w % 3 == 0 && h % 2 == 0) ok = true;
    if (w % 6 == 0 && h >= 5) ok = true;
    if (h % 6 == 0 && w >= 5) ok = true;
    if (w % 2 == 1 && w >= 5 && h % 6 == 0) ok = true;
    if (w % 11 == 0 && h % 2 == 0) ok = true;
    ok ? cout << "YES\n" : cout << "NO\n";
    exit(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int w, h, k;
    cin >> w >> h >> k;
    vector<array<int, 2>> tiled;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y; // w h
        x--;
        y--;
        tiled.push_back({y, x}); // h w
    }

    if (k == 0) subtask2(w, h, k, tiled);
    if (h <= 1000) subtask1(w, h, k, tiled);
    cout << "idk\n";
}

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