結果

問題 No.584 赤、緑、青の色塗り
ユーザー fiordfiord
提出日時 2017-10-28 00:29:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,569 bytes
コンパイル時間 1,102 ms
コンパイル使用メモリ 118,472 KB
実行使用メモリ 151,580 KB
最終ジャッジ日時 2024-05-01 18:22:29
合計ジャッジ時間 4,858 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 82 ms
12,416 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 WA -
testcase_11 AC 2 ms
5,376 KB
testcase_12 WA -
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

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