Submission #1214718

#TimeUsernameProblemLanguageResultExecution timeMemory
1214718JuanJLL-triominoes (CEOI21_ltriominoes)C++20
0 / 100
14 ms32840 KiB
#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;

    if((n%2==0&&m%3==0)||(n%3==0&&m%2==0)){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...