Submission #1186871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186871		Unforgettablepl	L-triominoes (CEOI21_ltriominoes)	C++20	0 / 100	8092 ms	9372 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 poss((1<<W),vector<bool>(1<<W));
    {
        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[mask1][mask2]=true;
            }
        }
    }
    vector<pair<int,int>> missing(K);
    for(auto&[a,b]:missing)cin>>b>>a;
    sort(missing.begin(),missing.end());
    auto combine = [&](vector<vector<bool>> &DP1,vector<vector<bool>> &DP2){
        vector DP((1<<W),vector<bool>(1<<W));
        for(int mask1=0;mask1<(1<<W);mask1++){
            for(int mask2=0;mask2<(1<<W);mask2++){
                for(int mask3=0;mask3<(1<<W);mask3++){
                    for(int mask4=0;mask4<(1<<W);mask4++){
                        if(DP1[mask1][mask3] and DP2[mask4][mask2] and poss[mask3][mask4]){
                            DP[mask1][mask2]=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;
    };
    auto ans = solve(H);
    if(ans[0][0])cout<<"YES\n";
    else cout << "NO\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20