#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 6;
int n,m,k;
ll dp[maxn][1<<maxn];
int g[maxn][maxn];
bool compat(int mask1, int mask2) {
for (int j=1; j<m; j++) {
vector<int> w(2,0);
for (int k=j-1; k<=j; k++) {
w[mask1>>k&1]++;
w[mask2>>k&1]++;
}
if (!(w[0]==2 && w[1]==2)) return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(g,-1,sizeof(g));
cin>>n>>m>>k;
while (k--) {
char op;
int r,c;
cin>>op>>r>>c;
--r; --c;
g[r][c]=(op=='+'?1:0);
}
for (int i=0; i<n; i++) {
for (int mask=0; mask<(1<<m); mask++) {
bool ok = true;
for (int j=0; j<m; j++) {
if (g[i][j]!=-1) {
if ((mask>>j&1)!=g[i][j]) {
ok = false;
}
}
}
if (!ok) continue;
if (i==0) {
dp[i][mask] = 1;
} else {
for (int pmask=0; pmask<(1<<m); pmask++) {
if (compat(pmask, mask)) {
dp[i][mask] += dp[i-1][pmask];
dp[i][mask] %= mod;
}
}
}
}
}
ll res = 0;
for (int mask=0; mask<(1<<m); mask++) {
res += dp[n-1][mask];
res %= mod;
}
cout<<res<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |