oj.uz

Submission #698673

# Submission time Handle Problem Language Result Execution time Memory
698673 2023-02-14T07:29:38 Z Cyanmond L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 515616 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);
                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) {
                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 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 81 ms 1740 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 155 ms 1640 KB Output is correct
12 Incorrect 23 ms 596 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 8093 ms 24084 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 8077 ms 515616 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 8087 ms 153892 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 8064 ms 21656 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 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 81 ms 1740 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 155 ms 1640 KB Output is correct
12 Incorrect 23 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -