Submission #1327316

#TimeUsernameProblemLanguageResultExecution timeMemory
1327316shirokuma5L-triominoes (CEOI21_ltriominoes)C++20
0 / 100
385 ms589824 KiB
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;

int main() {
    int w, h, k; cin >> w >> h >> k;
    vector<int> x(k), y(k);
    rep(i, k) cin >> x[i] >> y[i];

    if (k == w * h) {
        cout << "YES" << endl; return 0;
    }

    vector<vector<int>> board(h, vector<int> (w, 0));
    rep(i, k) board[y[i]-1][x[i]-1] = 1;

    int two = (1<<(w+1));
    vector<vector<bool>> dp(h * w + 1, vector<bool> (two, 0));
    int initial = 0;
    rep(i, w) {
        initial *= 2;
        if (board[0][i]) initial++;
    }
    initial *= 2;
    if (board[1][0]) initial++;
    dp[0][initial] = 1;
    rep(i, h-1) rep(j, w) {
        bool new_unit = 0;
        if (j+1 < w && board[i+1][j+1]) new_unit = 1;
        if (j == w-1 && i < h-2 && board[i+2][0]) new_unit = 1;
        rep(bi, two) if (dp[i*w+j][bi]) {
            bitset<15> bit(bi);
            // 何もしない
            dp[i*w+j+1][bi*2%two+new_unit] = 1;
            if (!bit.test(w)) {
                // j 行に横並び2つを置く
                if (j+1 < w && !bit.test(w-1)) {
                    if (!bit.test(0)) dp[i*w+j+1][bi*2%two+2+(1<<w)+new_unit] = 1;
                    if (!new_unit) dp[i*w+j+1][bi*2%two+1+(1<<w)] = 1;
                }
                if (j+1 < w && !bit.test(0) && !new_unit) {
                    dp[i*w+j+1][bi*2%two+3] = 1;
                }
                if (j > 0 && !bit.test(0) && !bit.test(1)) {
                    dp[i*w+j+1][bi*2%two+6+new_unit] = 1;
                }
            }
        }
    }
    if (dp[(h-1) * w][two-2]) cout << "YES" << endl;
    else cout << "NO" << endl;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...