結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:12:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,599 bytes
コンパイル時間 417 ms
コンパイル使用メモリ 81,656 KB
実行使用メモリ 86,632 KB
最終ジャッジ日時 2025-04-16 00:13:33
合計ジャッジ時間 4,748 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

n, R, G, B = map(int, input().split())
total = R + G + B
if total > n:
    print(0)
    exit()

from collections import defaultdict

current = defaultdict(int)
current[(0, 0, 0, 0, 0)] = 1  # (prev_color, streak, r, g, b)

for i in range(n):
    next_dp = defaultdict(int)
    for (prev_color, streak, r, g, b), cnt in current.items():
        # Option 1: Do not paint the current cell
        new_pc = 0
        new_streak = 0
        key = (new_pc, new_streak, r, g, b)
        next_dp[key] = (next_dp[key] + cnt) % MOD
        
        # Option 2: Paint the current cell, if possible
        if streak < 2:
            for color in [1, 2, 3]:
                if color == prev_color:
                    continue
                # Check if we can use this color
                if color == 1 and r >= R:
                    continue
                if color == 2 and g >= G:
                    continue
                if color == 3 and b >= B:
                    continue
                # Update counts
                nr = r + (1 if color == 1 else 0)
                ng = g + (1 if color == 2 else 0)
                nb = b + (1 if color == 3 else 0)
                if nr > R or ng > G or nb > B:
                    continue
                new_p = color
                new_s = streak + 1
                key_p = (new_p, new_s, nr, ng, nb)
                next_dp[key_p] = (next_dp[key_p] + cnt) % MOD
    current = next_dp

result = 0
for (pc, s, r, g, b), cnt in current.items():
    if r == R and g == G and b == B:
        result = (result + cnt) % MOD

print(result)
0