Submission #3016102

---

Source Code Expand

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * fh;
}

void File() {
#ifdef zjp_shadow
	freopen ("E.in", "r", stdin);
	freopen ("E.out", "w", stdout);
#endif
}

const int N = 310, Mod = 1e9 + 7;

int dp[N][N][N];
inline void Add(int &a, int b) {
	if ((a += b) >= Mod) a -= Mod;
}

int n, m;
typedef pair<int, int> PII;
#define fir first
#define sec second
#define mp make_pair
vector<PII> V[N];

int main () {

	File();

	n = read(); m = read();

	For (i, 1, m) { int l = read(), r = read(), x = read(); V[r].push_back(mp(l, x)); }

	dp[0][0][0] = 1;
	int ans = 0;
	For (i, 0, n) For (j, 0, i) For(k, 0, i) {
		if (!dp[i][j][k]) continue ;
		for (PII lim : V[i]) {
			int l = lim.fir, x = lim.sec, times = 1;
			if (l <= j) ++ times;
			if (l <= k) ++ times;
			if (times != x) { dp[i][j][k] = 0; break; }
		}
		if (!dp[i][j][k]) continue ;
		if (i == n) { Add(ans, dp[i][j][k]); }
		Add(dp[i + 1][i][k], dp[i][j][k]);
		Add(dp[i + 1][i][j], dp[i][j][k]);
		Add(dp[i + 1][j][k], dp[i][j][k]);
	}
	printf ("%d\n", ans);

    return 0;
}

Submission Info

Judge Result