Submission #3429972

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*
wa
*/

struct rgb{
	ll r,g,b;
};
bool operator<(const rgb &lhs, const rgb &rhs){//全順序を定義しなければいけない
    if(lhs.r < rhs.r){
    	return true;
    }else if(lhs.r == rhs.r){
    	if(lhs.g < rhs.g){
    		return true;
    	}else if(lhs.g == rhs.g){
    		if(lhs.b < rhs.b){
    			return true;
    		}
    	}
    }
    return false;
}

ll n,m,dp[310][310][310],ans=0;//(r,g,b)を最後に塗った場所
vector<mp> v[310];
set<rgb> s;

int main(void){
	rep(i,310)rep(j,310)rep(k,310)dp[i][j][k]=0;
	cin>>n>>m;
	rep(i,m){
		ll l,r,x;
		cin>>l>>r>>x;
		v[r].push_back(make_pair(l,x));
	}
	dp[0][0][0]=1;
	s.insert({0,0,0});
	reg(i,1,n+1){
		set<rgb> t;//遷移先
		for(auto itr = s.begin(); itr != s.end(); ++itr) {
			rgb x = *itr;
			ll r=x.r,g=x.g,b=x.b;
			// printf("%lld,%lld,%lld\n",r,g,b);
			bool ok=true;
			rep(j,v[i-1].size()){
				mp p=v[i-1][j];
				ll c=p.first,d=p.second,cnt=0;//l,x
				if(r>=c)cnt++;
				if(g>=c)cnt++;
				if(b>=c)cnt++;
				if(cnt!=d){
					ok=false;
					break;
				}
			}
			if(!ok)continue;
			if(i==n+1){
				ans+=dp[r][g][b];
			}else{
				dp[i][g][b]+=dp[r][g][b];
				dp[r][i][b]+=dp[r][g][b];
				dp[r][g][i]+=dp[r][g][b];
				t.insert({i,g,b});
				t.insert({r,i,b});
				t.insert({r,g,i});
			}
		}
		s=t;//遷移先の上書き
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result