oj.uz

Submission #698669

# Submission time Handle Problem Language Result Execution time Memory
698669 2023-02-14T07:27:49 Z Cyanmond L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 419432 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(s & (1 << b))) and (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 564 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 2 ms 560 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 983 ms 17412 KB Output is correct
9 Correct 1 ms 480 KB Output is correct
10 Correct 23 ms 912 KB Output is correct
11 Correct 2232 ms 17416 KB Output is correct
12 Incorrect 158 ms 1868 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 8092 ms 16656 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 8109 ms 419432 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 8061 ms 152732 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 8074 ms 16624 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 564 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 2 ms 560 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 983 ms 17412 KB Output is correct
9 Correct 1 ms 480 KB Output is correct
10 Correct 23 ms 912 KB Output is correct
11 Correct 2232 ms 17416 KB Output is correct
12 Incorrect 158 ms 1868 KB Output isn't correct
13 Halted 0 ms 0 KB -