Submission #3043731
Source Code Expand
/************************************************
* Au: Hany01
* Date: Aug 19th, 2018
* Prob: AGC017F Zigzag
* Email: hany01@foxmail.com
* Inst: Yali High School
************************************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int read() {
static int _, __; static char c_;
for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
const int maxn = 21, maxs = 1 << 20, maxk = maxn * maxn, MOD = 1e9 + 7;
struct Limits { int a, b, c; }lmt[maxk];
inline bool operator < (Limits A, Limits B) { return A.a < B.a; }
int n, m, k, f[2][maxn][maxs], all, cur, Ans, t;
inline void ad(int& x, int y) { if ((x += y) >= MOD) x -= MOD; }
int main()
{
#ifdef hany01
freopen("agc017f.in", "r", stdin);
freopen("agc017f.out", "w", stdout);
#endif
n = read() - 1, m = read(), k = read();
For(i, 1, k) lmt[i].a = read(), lmt[i].b = read(), lmt[i].c = read();
sort(lmt + 1, lmt + 1 + k);
f[0][n][0] = 1, all = 1 << n, cur = 1, t = 0;
For(i, 1, m) {
t ^= 1, Set(f[t], 0);
rep(j, all) f[t][0][j] = f[t ^ 1][n][j];
For(j, 1, n) rep(S, all) {
ad(f[t][j][S], f[t][j - 1][S]);
if (!(S >> (j - 1) & 1)) {
int nS = S | (1 << (j - 1));
For(k, j, n - 1) if (S >> k & 1) { nS ^= (1 << k); break; }
ad(f[t][j][nS], f[t][j - 1][S]);
}
}
while (cur <= k && lmt[cur].a == i) {
rep(S, all) if ((S ^ ((lmt[cur].c) << (lmt[cur].b - 1))) & (1 << (lmt[cur].b - 1))) f[t][n][S] = 0;
++ cur;
}
}
rep(S, all) ad(Ans, f[t][n][S]);
printf("%d\n", Ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Zigzag |
User |
Hany01 |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2596 Byte |
Status |
AC |
Exec Time |
1478 ms |
Memory |
172288 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All |
sample1.txt, sample2.txt, sample3.txt, sample4.txt, a1.txt, a10.txt, a11.txt, a12.txt, a13.txt, a2.txt, a3.txt, a4.txt, a5.txt, a6.txt, a7.txt, a8.txt, a9.txt, b1.txt, b10.txt, b11.txt, b12.txt, b13.txt, b14.txt, b15.txt, b16.txt, b17.txt, b2.txt, b3.txt, b4.txt, b5.txt, b6.txt, b7.txt, b8.txt, b9.txt, n18.txt, n19.txt, n20.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt |
Case Name |
Status |
Exec Time |
Memory |
a1.txt |
AC |
95 ms |
172288 KB |
a10.txt |
AC |
1269 ms |
172288 KB |
a11.txt |
AC |
1194 ms |
172288 KB |
a12.txt |
AC |
1193 ms |
172288 KB |
a13.txt |
AC |
1147 ms |
172288 KB |
a2.txt |
AC |
95 ms |
172288 KB |
a3.txt |
AC |
95 ms |
172288 KB |
a4.txt |
AC |
157 ms |
172288 KB |
a5.txt |
AC |
241 ms |
172288 KB |
a6.txt |
AC |
1472 ms |
172288 KB |
a7.txt |
AC |
1388 ms |
172288 KB |
a8.txt |
AC |
1409 ms |
172288 KB |
a9.txt |
AC |
1342 ms |
172288 KB |
b1.txt |
AC |
280 ms |
172288 KB |
b10.txt |
AC |
1329 ms |
172288 KB |
b11.txt |
AC |
1220 ms |
172288 KB |
b12.txt |
AC |
1180 ms |
172288 KB |
b13.txt |
AC |
1169 ms |
172288 KB |
b14.txt |
AC |
1185 ms |
172288 KB |
b15.txt |
AC |
1210 ms |
172288 KB |
b16.txt |
AC |
1221 ms |
172288 KB |
b17.txt |
AC |
1243 ms |
172288 KB |
b2.txt |
AC |
691 ms |
172288 KB |
b3.txt |
AC |
268 ms |
172288 KB |
b4.txt |
AC |
121 ms |
172288 KB |
b5.txt |
AC |
280 ms |
172288 KB |
b6.txt |
AC |
140 ms |
172288 KB |
b7.txt |
AC |
1467 ms |
172288 KB |
b8.txt |
AC |
1436 ms |
172288 KB |
b9.txt |
AC |
1381 ms |
172288 KB |
n18.txt |
AC |
497 ms |
172288 KB |
n19.txt |
AC |
806 ms |
172288 KB |
n20.txt |
AC |
1478 ms |
172288 KB |
sample1.txt |
AC |
57 ms |
172288 KB |
sample2.txt |
AC |
57 ms |
172288 KB |
sample3.txt |
AC |
82 ms |
172288 KB |
sample4.txt |
AC |
1478 ms |
172288 KB |