Submission #1183380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183380		Mighilon	L-triominoes (CEOI21_ltriominoes)	C++20	10 / 100	396 ms	589824 KiB

ltrominoes

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const ll MOD = 998244353;
const int mxN = 3e5+5;

void solve(){
    // int w,h;
    // cin>>w>>h;
    // vector<vector<vl>> dp(h+2,vector<vl>(w+2,vl(1<<(w+1))));
    // dp[0][1][0]=1;
    // #define _s(i) ((s>>(i))&1)
    // F0R(i,h){
    //     FOR(j,1,w+1){
    //         F0R(s,1<<(w+1)){
    //             if(!dp[i][j][s])continue;
    //             if(_s(j)){
    //                 dp[i][j+1][s^(1<<j)]+=dp[i][j][s];
    //             }
    //             // #     ##   ##    #
    //             // ##     #   #    ##
    //             if(j<w&&!_s(j)&&!_s(j-1)&&!_s(j+1)){
    //                 dp[i][j+1][s^(1<<(j-1))^(1<<(j+1))]+=dp[i][j][s];
    //             }
    //             if(j>=2&&!_s(j)&&!_s(j-1)&&!_s(j-2)){
    //                 dp[i][j+1][s^(1<<(j-1))^(1<<(j-2))]+=dp[i][j][s];
    //             }
    //             if(j<w&&!_s(j)&&!_s(j-1)){
    //                 dp[i][j+1][s^(1<<j)^(1<<(j-1))]+=dp[i][j][s];
    //             }
    //             if(j<w&&!_s(j)&&!_s(j+1)){
    //                 dp[i][j+1][s^(1<<j)^(1<<(j+1))]+=dp[i][j][s];
    //             }
    //         }
    //     }
    //     F0R(s,1<<(w)){
    //         dp[i+1][1][s<<1]=dp[i][w+1][s];
    //     }
    // }
    // cout<<dp[h][1][0]<<nl;
    int w,h,k;
    cin>>w>>h>>k; 
    vpi p(k);

    F0R(i,k){
        cin>>p[i].f>>p[i].s;
        p[i].f--;p[i].s--;
    }
    // if((1LL*w*h-k)%3!=0){
    //     cout<<"NO"<<nl;
    //     return;
    // }
    sort(all(p),[](pi& a,pi & b){return a.s<b.s;});
    // h=0;
    // vi he(k);
    // F0R(i,k){
    //     if(i) he[i]=he[i-1]+min(p[i].s-he[i-1],(p[i].f-he[i-1]-1)%10+10);
    //     else he[i]=min(he[i],he[i]%10+10);
    //     h=he[i];
    // }
    vector<vi> dp(w+2,vi(1<<(w+1)));
    vector<vi> a(h+2,vi(w));
    int s_=0;
    F0R(i,k){
        a[p[i].s][p[i].f]=1;
        if(!p[i].s)
            s_|=(1<<p[i].f);
    }
    dp[1][s_<<1]=1;
    #define _s(i) ((s>>(i))&1)
    F0R(i,h){
        dbg(i,dp)
        // F0R(s,1<<(w+1)){
        //     if(!dp[1][s])continue;
        //     string tmp="";
        //     F0R(k,w+1){
        //         if(_s(k))tmp.pb('#');
        //         else tmp.pb('.');
        //     }
        //     dbg(i,s,tmp);
        // }

        FOR(j,1,w+1){
            F0R(s,1<<(w+1)){
                if(!dp[j][s])continue;
                if(_s(j)){
                    dp[j+1][s^(1<<j)]|=dp[j][s];
                }
                if(a[i][j-1]&&!_s(j)){
                    dp[j+1][s]|=dp[j][s];
                }
                // #  ## ##  #
                // ##  # #  ##
                if(j<w&&!_s(j)&&!_s(j-1)&&!_s(j+1)&&!a[i][j-1]&&!a[i][j]&&!a[i+1][j-1]){
                    dp[j+1][s^(1<<(j-1))^(1<<(j+1))]|=dp[j][s];
                }
                if(j>=2&&!_s(j)&&!_s(j-1)&&!_s(j-2)&&!a[i][j-1]&&!a[i+1][j-1]&&!a[i+1][j-2]){
                    dp[j+1][s^(1<<(j-2))^(1<<(j-1))]|=dp[j][s];
                }
                if(j<w&&!_s(j)&&!_s(j-1)&&!a[i][j-1]&&!a[i+1][j-1]&&!a[i+1][j]){
                    dp[j+1][s^(1<<(j))^(1<<(j-1))]|=dp[j][s];
                }
                if(j<w&&!_s(j)&&!_s(j+1)&&!a[i][j-1]&&!a[i][j]&&!a[i+1][j]){
                    dp[j+1][s^(1<<(j))^(1<<(j+1))]|=dp[j][s];
                }
            }
        }
        dbg(i,dp)
        F0R(s,1<<(w+1)){
            dp[1][s]=0;
        }
        F0R(s,1<<(w)){
            dp[1][s<<1]=dp[w+1][s];
        }
        FOR(j,2,w+2){
            F0R(s,1<<(w+1)){
                dp[j][s]=0;
            }
        }
    }
    dbg(dp)
    if(dp[1][0])
        cout<<"YES"<<nl;
    else cout<<"NO"<<nl;
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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