Submission #1327335

#TimeUsernameProblemLanguageResultExecution timeMemory
1327335shirokuma5L-triominoes (CEOI21_ltriominoes)C++20
10 / 100
383 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;

void print(const vector<bool> &a) {
    for (bool b : a) cerr << " " << b;
    cerr << endl;
}

int main() {
    // Input
    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)); // 欠けていたら 1(true)
    rep(i, k) board[y[i]-1][x[i]-1] = 1;

    int two = (1<<(w+1));
    vector<vector<bool>> dp(h * w, vector<bool> (two, 0));
    int initial = 0; // はじめの w+1 マスが存在するかどうか
    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]) {
            //cerr << i << " " << j << " " << bi << endl;
            bitset<15> bit(bi);
            if (bit.test(w)) {
                //cerr << "! " << bi*2%two+new_unit << endl;
                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)) {
                    // (i,j),(i,j+1),(i+1,j)
                    //cerr << "!! " << bi*2%two+2+(1<<w)+new_unit << endl;
                    if (!bit.test(0)) dp[i*w+j+1][bi*2%two+2+(1<<w)+new_unit] = 1;
                    // (i,j),(i,j+1),(i+1,j+1)
                    //cerr << "!!! " << bi*2%two+1+(1<<w) << endl;
                    if (!new_unit) dp[i*w+j+1][bi*2%two+1+(1<<w)] = 1;
                }
                // (i,j),(i+1,j+1),(i+1,j) に置く
                if (j+1 < w && !bit.test(0) && !new_unit) {
                    //cerr << "!!!! " << bi*2%two+3 << endl;
                    dp[i*w+j+1][bi*2%two+3] = 1;
                }
                // (i,j),(i+1,j),(i+1,j-1) に置く
                if (j > 0 && !bit.test(0) && !bit.test(1)) {
                    //cerr << "!!!!! " << bi*2%two+6+new_unit << endl;
                    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;
    return 0;

    rep(i, w * h) {
        cerr << i << " :"; print(dp[i]);
    }

}
#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...