Submission #1214676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214676		JuanJL	L-triominoes (CEOI21_ltriominoes)	C++20	0 / 100	42 ms	65008 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 long long ll;


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

bool mp[MAXN][MAXM];

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;
    }

    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){
            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;

    vector<ll> opt;
    ll z = 0; forn(i,0,m) if(mp[x+1][i]) z|=(1<<i);
    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: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20