結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー fiord
提出日時 2017-10-28 00:29:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,569 bytes
コンパイル時間 1,055 ms
コンパイル使用メモリ 116,940 KB
実行使用メモリ 190,720 KB
最終ジャッジ日時 2024-11-22 00:06:15
合計ジャッジ時間 19,978 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 6 WA * 2 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <random>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0

const ll inf = (ll)1e9;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

map<tuple<int, int, int, int ,bool>, ll> dp;

//赤青、青緑、緑赤で塗れるだけ塗る（2^個数通り）
//余ったところに単色を塗っていく
//ここで塗り切れるか判定が出来る
bool check(int n, int r, int g, int b) {
	int use = 0;
	int rg = min(r, g);
	use += max(0, 3 * rg - 1);
	r -= rg;	g -= rg;
	int gb = min(g, b);
	use += max(0, 3 * gb - (use == 0 ? 1 : 0));
	g -= gb;	b -= gb;
	int br = min(b, r);
	use += max(0, 3 * br - (use == 0 ? 1 : 0));
	b -= br;	r -= br;
	use += max(0, 2 * (r + g + b) - (use == 0 ? 1 : 0));
	if (use <= n) return true;
	else	return false;
}

ll solve(int n, int a, int b, int c,bool f) {
	if (dp.find(mt(n, a, b, c, f)) != dp.end())	return dp[mt(n, a, b, c, f)];
	if (n < 0)	return 0;
	if (n >= 0 && a + b + c == 0)	return 1;
	if (!check(n, a, b, c))	return 0;
	if (!f)	return dp[mt(n, a, b, c, f)] = solve(n - 1, a, b, c, true);
	ll ret = 0;
	vint dat = { a, b, c };
	rep(i, 2){
		if (a - i < 0)	continue;
		rep(j, 2) {
			if (b - j < 0)	continue;
			rep(k, 2) {
				if (c - k < 0)	continue;
				if (i == j&&j == k)	continue;
				ret += (i + j + k)*solve(n - (i + j + k), a - i, b - j, c - k, false);
			}
		}
	}
	ret += solve(n - 1, a, b, c, true);
	return dp[mt(n, a, b, c, f)] = ret%mod;
}

int main() {
	int n, r, g, b;	cin >> n >> r >> g >> b;
	cout << solve(n, r, g, b, true) << endl;
	return 0;
}
0