Submission #1518380

---

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

Judge Result