제출 #1214701

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

ltrominoes

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef int ll;


const int MAXN = 1000+5;
const int MAXM = 13+5;
const int MAXP = 8200;

bool mp[MAXN][MAXM];
bool used[MAXP];
vector<ll> optt[MAXP];

ll n,m; 

struct F{
    vector<ll> u;
    vector<ll> d;
    F(vector<ll> u,vector<ll> d):u(u),d(d){}
};

vector<F> fig={F({0,1},{0}),F({0,1},{1}),F({1},{0,1}),F({0},{0,1})};

void make_comb(ll x, ll y, ll z, vector<ll> &opt){
    if(x>=m-1){
        if(y==(1<<m)-1) opt.pb(z);
        return;
    }

    if(y&(1<<x)) make_comb(x+1,y,z,opt);

    for(auto i:fig){
        bool puede = true;

        ll newy = y;
        ll newz = z;

        for(auto j:i.u){
            newy|=(1<<(x+j));
            if(y&(1<<(x+j))){
                puede=false;
            }
        }

        for(auto j:i.d){
            newz|=(1<<(x+j));
            if(z&(1<<(x+j))){
                puede=false;
            }
        }

        if(puede && newy&(1<<x)){
            make_comb(x+1,newy,newz,opt);
        }
    }
}

ll dp[MAXN][MAXP];

ll f(ll x,ll y){
    ll &res = dp[x][y];
    if(res!=-1) return res;
    if(x>=n-1){
        if(y==(1<<m)-1) return 1;
        return 0;
    }

    res=0;

    
    ll z = 0; forn(i,0,m) if(mp[x+1][i]) z|=(1<<i);

    if(z==0){
        if(!used[y]){
            make_comb(0,y,z,optt[y]);
            used[y]=true;
        }

        for(auto i:optt[y]){
            res=max(res,f(x+1,i));
        }

        return res;
    }

    vector<ll> opt;
    make_comb(0,y,z,opt);

    for(auto i:opt){
        res=max(res,f(x+1,i));
    }
    return res;
}

int main(){FIN;
    mset(dp,-1);
    cin>>m>>n; 
    ll k; cin>>k;

    ll u,v;
    forn(i,0,k){
        cin>>u>>v; u--; v--;
        mp[v][u]=true;
    }

    ll y = 0; forn(i,0,m) if(mp[0][i]) y|=(1<<i);

    ll res = f(0,y);
    cout<<(res?"YES":"NO")<<'\n';

    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