Submission #1125279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125279		Bananabread	L-triominoes (CEOI21_ltriominoes)	C++20	0 / 100	10 ms	5956 KiB

ltrominoes

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "MOTOR"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll dp[1<<13][13][1001];
ll arr[14][1002];
ll n,m,k;
void solve(){
    cin>>m>>n>>k;
    if((n*m-k)%3!=0){
        cout<<"NO\n";
        return ;
    }
    if(k==0){
        if(n%3==0&&m%2==0){
            cout<<"YES\n";
            return ;
        }
        if(n%2==0&&m%3==0){
            cout<<"YES\n";
            return ;
        }
        cout<<"NO\n";
        return;
    }
    else{
        for(int i=1;i<=k;i++){
            ll x,y;
            cin>>x>>y;
            x--;
            arr[y][x]=1;
        }
        dp[0][0][1]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<m;j++){
                for(int mask=0;mask<(1<<m);mask++){
                    if(!dp[mask][j][i]) continue;
                    if(arr[i][j]||(mask&(1<<j))){
                        dp[mask^(arr[i+1][j]<<j)][j+1][i]=1;
                        continue;
                    }
                    if(!arr[i][j+1]&&!arr[i+1][j]){
                        dp[mask^(1<<j)^(arr[i+1][j+1]<<(j+1))][j+2][i]=1;
                    }
                    if(!arr[i][j+1]&&!arr[i+1][j+1]){
                        dp[mask^(1<<j)^(arr[i+1][j]<<(j+1))][j+2][i]=1;
                    }
                    if(!arr[i][j+1]&&!arr[i+1][j+1]){
                        dp[mask^(arr[i+1][j]<<j)^(1<<(j+1))][j+2][i]=1;
                    }
                    if(arr[i][j+1]){
                        if(!arr[i+1][j]&&!arr[i+1][j+1]){
                            dp[mask^(1<<j)^(1<<(j+1))][j+2][i]=1;
                        }
                    }
                    if(j){
                        if(!arr[i+1][j-1]&&!arr[i+1][j]){
                            dp[mask^(1<<j)^(1<<(j-1))][j+1][i]=1;
                        }
                    }
                }
            }
            for(int mask=0;mask<(1<<m);mask++){
                dp[mask][0][i+1]=dp[mask][m][i];
            }
        }
        if(dp[0][0][n+1]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
        memset(dp,0,sizeof(dp));
        memset(arr,0,sizeof(arr));
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    ll t;
    cin>>t;
    while(t--) solve();
}

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