Submission #3773205

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int maxn = 305, mod = 1e9 + 7;

int n, m;
int f[maxn][maxn][maxn];
vector<pair<int, int> > vec[maxn];

inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

inline void inc(int &a, int b) {a += b; if (a >= mod) a -= mod;}

inline bool check(int r, int j, int k)
{
	for (int i = 0; i < vec[r].size(); ++i)
		if (1 + (vec[r][i].first <= j) + (vec[r][i].first <= k) != vec[r][i].second) return 0;
	return 1;
}

int main()
{
	n = gi(); m = gi();
	for (int l, r, x, i = 1; i <= m; ++i) {
		l = gi(); r = gi(); x = gi();
		vec[r].push_back(make_pair(l, x));
	}

	if (check(1, 0, 0)) f[1][0][0] = 3;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j < i; ++j)
			for (int k = 0; k < i; ++k) {
				if (!f[i][j][k]) continue;
				if (check(i + 1, j, k))
					inc(f[i + 1][j][k], f[i][j][k]);
				if (check(i + 1, i, k))
					inc(f[i + 1][i][k], f[i][j][k]);
				if (check(i + 1, j, i))
					inc(f[i + 1][j][i], f[i][j][k]);
			}

	int ans = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			inc(ans, f[n][i][j]);
	printf("%d\n", ans);
	
	return 0;
}

Submission Info

Judge Result