Submission #1186898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186898		Unforgettablepl	L-triominoes (CEOI21_ltriominoes)	C++20	28 / 100	8095 ms	10636 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);
    }
    auto combine = [&](vector<vector<bool>> &DP1,vector<vector<bool>> &DP2){
        if(DP1.empty())return 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(auto&[mask3,mask4]:poss){
                    if(DP1[mask1][mask3] and DP2[mask4][mask2]){
                        DP[mask1][mask2]=true;
                        break;
                    }
                }
            }
        }
        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;
    int last = 0;
    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;
        }
        if(tim!=last+1){
            auto t = solve(tim-last-1);
            ans = combine(ans,t);
        }
        ans = combine(ans,DPmy);
        last = tim;
    }
    if(H!=last){
        auto t = solve(H-last);
        ans = combine(ans,t);
    }
    if(ans[0][0])cout<<"YES\n";
    else cout << "NO\n";
}

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