#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=1;
//cin>>t;
while(t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |