#212430 (C++14) No.584 赤、緑、青の色塗り

• 問題: No.584 赤、緑、青の色塗り
• ユーザー: fiord
• 提出日時: 2017-10-28 00:29:23
• 言語: C++14 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 10,496 KB
testcase_01	AC	2 ms; 10,496 KB
testcase_02	AC	2 ms; 10,496 KB
testcase_03	AC	2 ms; 10,496 KB
testcase_04	AC	2 ms; 10,496 KB
testcase_05	AC	83 ms; 17,792 KB
testcase_06	AC	2 ms; 12,068 KB
testcase_07	AC	2 ms; 10,496 KB
testcase_08	AC	2 ms; 10,496 KB
testcase_09	AC	2 ms; 10,496 KB
testcase_10	WA	-
testcase_11	AC	2 ms; 5,248 KB
testcase_12	WA	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	2 ms; 5,248 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-

ソースコード

#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;
}