Submission #3043717
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, nex[maxn][maxs];
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;
Set(nex, -1);
rep(j, n) rep(S, all)
For(k, j, n - 1) if (S >> k & 1) { nex[j][S] = k; break; }
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));
if (nex[j][S] >= 0) nS ^= (1 << nex[j][S]);
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 |
0 |
Code Size |
2703 Byte |
Status |
MLE |
Exec Time |
1487 ms |
Memory |
258304 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
MLE |
122 ms |
258304 KB |
a10.txt |
MLE |
1280 ms |
258304 KB |
a11.txt |
MLE |
1200 ms |
258304 KB |
a12.txt |
MLE |
1207 ms |
258304 KB |
a13.txt |
MLE |
1159 ms |
258304 KB |
a2.txt |
MLE |
122 ms |
258304 KB |
a3.txt |
MLE |
122 ms |
258304 KB |
a4.txt |
MLE |
183 ms |
258304 KB |
a5.txt |
MLE |
265 ms |
258304 KB |
a6.txt |
MLE |
1477 ms |
258304 KB |
a7.txt |
MLE |
1384 ms |
258304 KB |
a8.txt |
MLE |
1417 ms |
258304 KB |
a9.txt |
MLE |
1352 ms |
258304 KB |
b1.txt |
MLE |
307 ms |
258304 KB |
b10.txt |
MLE |
1335 ms |
258304 KB |
b11.txt |
MLE |
1227 ms |
258304 KB |
b12.txt |
MLE |
1196 ms |
258304 KB |
b13.txt |
MLE |
1203 ms |
258304 KB |
b14.txt |
MLE |
1222 ms |
258304 KB |
b15.txt |
MLE |
1249 ms |
258304 KB |
b16.txt |
MLE |
1258 ms |
258304 KB |
b17.txt |
MLE |
1282 ms |
258304 KB |
b2.txt |
MLE |
721 ms |
258304 KB |
b3.txt |
MLE |
297 ms |
258304 KB |
b4.txt |
MLE |
152 ms |
258304 KB |
b5.txt |
MLE |
306 ms |
258304 KB |
b6.txt |
MLE |
187 ms |
258304 KB |
b7.txt |
MLE |
1476 ms |
258304 KB |
b8.txt |
MLE |
1439 ms |
258304 KB |
b9.txt |
MLE |
1380 ms |
258304 KB |
n18.txt |
MLE |
518 ms |
258304 KB |
n19.txt |
MLE |
822 ms |
258304 KB |
n20.txt |
MLE |
1483 ms |
258304 KB |
sample1.txt |
MLE |
84 ms |
258304 KB |
sample2.txt |
MLE |
85 ms |
258304 KB |
sample3.txt |
MLE |
110 ms |
258304 KB |
sample4.txt |
MLE |
1487 ms |
258304 KB |