Submission #1518385
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define maxn 302
#define FOR(i, l, r) for (int i=l; i<=r; ++i)
#define FORD(i, r, l) for (int i=r; i>=l; --i)
#define REP(i, r) for (int i=0; i<(int)r; ++i)
#define REPD(i, r) for (int i=(int)r-1; i>=0; --i)
#define fi first
#define se second
#define mk make_pair
#define nil NULL
#define y0 __y0
#define y1 __y1
#define x0 __x0
#define x1 __x1
#define next __next
#define sz size
#define Debug(X) {cerr << #X << " = " << X << '\n';}
#define PR(A, n) {cerr << #A << " = "; FOR(i, 1, n) cerr << A[i] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; REP(i, n) cerr << A[i] << ' '; cerr << '\n';}
typedef long long ll;
typedef double db;
typedef pair<db, db> dd;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int inf = 1e9;
const ll MOD = 1000000007;
template<class T> int getbit(T x, int pos) {return (x>>(pos-1)) & 1;}
template<class T> void turn_on(T &x, int pos) {x = x | ((T)1<<(pos-1));}
template<class T> void turn_off(T &x, int pos) {x = x & ~((T)1<<(pos-1));}
template<class T> T sqr(T a) {return a*a;}
int n, m;
vector<ii> R[maxn];
ll f[maxn][maxn][maxn][4];
bool check(int i, int x, int y, int z) {
int x1, y1, z1;
if (z==0) {
x1 = i; y1= x; z1 = y;
}
else if (z==1) {
x1 = x; y1 = i; z1 = y;
}
else {
x1 = x; y1 = y; z1 = i;
}
REP(j, R[i].sz()) {
int l = R[i][j].fi, cnt = 0;
if (x1>=l) ++cnt;
if (y1>=l) ++cnt;
if (z1>=l) ++cnt;
if (cnt<R[i][j].se) return false;
}
return true;
}
ll dp(int i, int x, int y, int z) {
if (f[i][x][y][z]>-1) return f[i][x][y][z];
if (i==n) return check(i, x, y, z);
f[i][x][y][z] = 0;
if (!check(i, x, y, z)) return f[i][x][y][z] = 0;
if (z==0) {
f[i][x][y][z] += dp(i+1, x, y, z) + dp(i+1, i, y, 1) + dp(i+1, i, x, 2);
}
else if (z==1) {
f[i][x][y][z] += dp(i+1, x, y, z) + dp(i+1, i, y, 0) + dp(i+1, x, i, 2);
}
else {
f[i][x][y][z] += dp(i+1, x, y, z) + dp(i+1, y, i, 0) + dp(i+1, x, i, 1);
}
return f[i][x][y][z]%=MOD;
}
int main() {
//freopen("rgb.inp", "r", stdin);
//freopen(".out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
FOR(i, 1, m) {
int l, r, x; cin >> l >> r >> x;
R[r].push_back(ii(l, x));
}
memset(f, -1, sizeof(f));
//Debug(dp(1, 0, 0, 0));
cout << dp(1, 0, 0, 0) + dp(1, 0, 0, 1) + dp(1, 0, 0, 2);
}
Submission Info
Submission Time |
|
Task |
E - RGB Sequence |
User |
phong22kk11 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2571 Byte |
Status |
MLE |
Exec Time |
1319 ms |
Memory |
861184 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
MLE |
208 ms |
861056 KB |
0_01.txt |
MLE |
207 ms |
861056 KB |
0_02.txt |
MLE |
208 ms |
861056 KB |
0_03.txt |
MLE |
208 ms |
861056 KB |
1_00.txt |
MLE |
221 ms |
861056 KB |
1_01.txt |
MLE |
211 ms |
861056 KB |
1_02.txt |
MLE |
209 ms |
861056 KB |
1_03.txt |
MLE |
231 ms |
861056 KB |
1_04.txt |
MLE |
230 ms |
861056 KB |
1_05.txt |
MLE |
215 ms |
861056 KB |
1_06.txt |
MLE |
210 ms |
861056 KB |
1_07.txt |
MLE |
232 ms |
861056 KB |
1_08.txt |
MLE |
307 ms |
861056 KB |
1_09.txt |
MLE |
285 ms |
861056 KB |
1_10.txt |
MLE |
239 ms |
861056 KB |
1_11.txt |
MLE |
249 ms |
861056 KB |
1_12.txt |
MLE |
358 ms |
861184 KB |
1_13.txt |
MLE |
270 ms |
861056 KB |
1_14.txt |
MLE |
251 ms |
861056 KB |
1_15.txt |
MLE |
308 ms |
861056 KB |
1_16.txt |
MLE |
239 ms |
861056 KB |
1_17.txt |
MLE |
214 ms |
861056 KB |
1_18.txt |
MLE |
232 ms |
861056 KB |
1_19.txt |
MLE |
219 ms |
861056 KB |
1_20.txt |
MLE |
376 ms |
861056 KB |
1_21.txt |
MLE |
271 ms |
861056 KB |
1_22.txt |
MLE |
306 ms |
861056 KB |
1_23.txt |
MLE |
311 ms |
861056 KB |
1_24.txt |
MLE |
496 ms |
861056 KB |
1_25.txt |
MLE |
355 ms |
861056 KB |
1_26.txt |
MLE |
333 ms |
861056 KB |
1_27.txt |
MLE |
305 ms |
861056 KB |
1_28.txt |
MLE |
465 ms |
861056 KB |
1_29.txt |
MLE |
439 ms |
861056 KB |
1_30.txt |
MLE |
320 ms |
861056 KB |
1_31.txt |
MLE |
446 ms |
861056 KB |
1_32.txt |
MLE |
1082 ms |
861056 KB |
1_33.txt |
MLE |
547 ms |
861056 KB |
1_34.txt |
MLE |
619 ms |
861056 KB |
1_35.txt |
MLE |
853 ms |
861056 KB |
1_36.txt |
MLE |
1237 ms |
861056 KB |
1_37.txt |
MLE |
1291 ms |
861056 KB |
1_38.txt |
MLE |
1076 ms |
861056 KB |
1_39.txt |
MLE |
609 ms |
861056 KB |
1_40.txt |
MLE |
1319 ms |
861056 KB |
1_41.txt |
MLE |
223 ms |
861056 KB |
1_42.txt |
MLE |
208 ms |
861056 KB |