Submission #3422041

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 305;
const int MAX_M = 305;

int N, M;
int dp[MAX_N][MAX_N][MAX_N];

class Strict {
public:
  int l, x;
};

vector<Strict> S[MAX_N];

signed main()
{
  cin >> N >> M;
  REP(i,M) {
    Strict s;
    int r; cin >> s.l >> r >> s.x;
    S[r].push_back(s);
  }

  memset(dp,0,sizeof(dp));

  dp[0][0][0] = 1;

  REP(r,N+1) {
    REP(g,N+1) {
      REP(b,N+1) {
        if(dp[r][g][b] == 0) {
          continue;
        }
        
        int p = max(r, max(g, b));

        for(const auto& s : S[p]) {
          int cnt = (s.l <= r) + (s.l <= g) + (s.l <= b);
          if(cnt != s.x) {
            dp[r][g][b] = 0;
            break;
          }
        }

				dp[p + 1][g][b] = (dp[p + 1][g][b] + dp[r][g][b]) % MOD;
				dp[r][p + 1][b] = (dp[r][p + 1][b] + dp[r][g][b]) % MOD;
				dp[r][g][p + 1] = (dp[r][g][p + 1] + dp[r][g][b]) % MOD;
      }
    }
  }

  int ans = 0;
  REP(i,N) {
    REP(j,N) {
      ans += dp[N][i][j] + dp[i][N][j] + dp[i][j][N];
      ans %= MOD;
    }
  }

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result