제출 #1186916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186916		Unforgettablepl	L-triominoes (CEOI21_ltriominoes)	C++20	10 / 100	5045 ms	589824 KiB

ltrominoes

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int W,H,K;
    cin >> W >> H >> K;
    vector<pair<int,int>> poss;
    {
        for(int mask1=0;mask1<(1<<W);mask1++){
            for(int mask2=0;mask2<(1<<W);mask2++){
                bool extra = false;
                bool doublesause = false;
                bool works = true;
                for(int i=0;i<W;i++){
                    if(doublesause){
                        doublesause = false;
                        if(!(mask1&(1<<i)) or !(mask2&(1<<i)))works=false;
                    } else if(extra){
                        extra=false;
                        if(!(mask1&(1<<i)) and !(mask2&(1<<i)))works=false;
                        if((mask1&(1<<i)) and (mask2&(1<<i)))doublesause=true;
                    } else {
                        if((mask1&(1<<i)) and (mask2&(1<<i)))extra=true;
                        else if((mask1&(1<<i)) or (mask2&(1<<i)))doublesause=true;
                    }
                }
                if(extra or doublesause)works=false;
                if(works)poss.emplace_back(mask1,mask2);
            }
        }
    }
    map<int,vector<int>> missing;
    for(int i=1;i<=K;i++){
        int a,b;cin>>a>>b;
        missing[b].emplace_back(a);
    }
    for(int i=1;i<=H;i++)missing[i];
    auto combine = [&](vector<vector<bool>> &DP1,vector<vector<bool>> &DP2,int cantmask){
        if(DP1.empty())return DP2;
        vector DP((1<<W),vector<bool>(1<<W));
        for(auto&[mask3,mask4]:poss){
            if(DP1[0][mask3] and DP2[mask4][mask4^((1<<W)-1)^cantmask]){
                DP[0][mask4^((1<<W)-1)^cantmask]=true;
            }
        }
        return DP;
    };
    vector DPbase((1<<W),vector<bool>(1<<W));
    for(int mask=0;mask<(1<<W);mask++)DPbase[mask][mask^((1<<W)-1)]=true;
    // function<vector<vector<bool>>(int)> solve = [&](int a){
    //     if(a==1)return DPbase;
    //     auto curr = solve(a>>1);
    //     curr = combine(curr,curr);
    //     if(a&1)curr=combine(curr,DPbase);
    //     return curr;
    // };
    vector<vector<bool>> ans;
    for(auto [tim,things]:missing){
        int cantmask = 0;
        for(int&i:things)cantmask|=(1<<(i-1));
        vector DPmy((1<<W),vector<bool>(1<<W));
        for(int mask=0;mask<(1<<W);mask++){
            if(cantmask&mask)continue;
            DPmy[mask][mask^((1<<W)-1)^cantmask]=true;
        }
        ans = combine(ans,DPmy,cantmask);
    }
    if(ans[0][0])cout<<"YES\n";
    else cout << "NO\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