結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:27:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,293 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,768 KB |
実行使用メモリ | 82,488 KB |
最終ジャッジ日時 | 2025-06-12 13:33:34 |
合計ジャッジ時間 | 4,955 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 7 TLE * 1 -- * 6 |
ソースコード
MOD = 10**9 + 7 def main(): import sys from collections import defaultdict N, R, G, B = map(int, sys.stdin.readline().split()) total = R + G + B if total > N: print(0) return # Initialize DP with (prev_color, streak, r_remain, g_remain, b_remain) # prev_color: 0=R, 1=G, 2=B, 3=blank dp = defaultdict(int) initial_state = (3, 0, R, G, B) dp[initial_state] = 1 for _ in range(N): next_dp = defaultdict(int) for (prev_color, streak, r, g, b), cnt in dp.items(): # Option 1: Place blank new_streak = 0 new_pc = 3 key = (new_pc, new_streak, r, g, b) next_dp[key] = (next_dp[key] + cnt) % MOD # Option 2: Place Red if r > 0 and prev_color != 0: if streak < 2: new_r = r - 1 new_streak = streak + 1 if prev_color != 3 else 1 new_pc = 0 if new_streak <= 2 and new_r >= 0: key = (new_pc, new_streak, new_r, g, b) next_dp[key] = (next_dp[key] + cnt) % MOD # Option 3: Place Green if g > 0 and prev_color != 1: if streak < 2: new_g = g - 1 new_streak = streak + 1 if prev_color != 3 else 1 new_pc = 1 if new_streak <= 2 and new_g >= 0: key = (new_pc, new_streak, r, new_g, b) next_dp[key] = (next_dp[key] + cnt) % MOD # Option 4: Place Blue if b > 0 and prev_color != 2: if streak < 2: new_b = b - 1 new_streak = streak + 1 if prev_color != 3 else 1 new_pc = 2 if new_streak <= 2 and new_b >= 0: key = (new_pc, new_streak, r, g, new_b) next_dp[key] = (next_dp[key] + cnt) % MOD dp = next_dp result = 0 for (pc, s, r, g, b), cnt in dp.items(): if r == 0 and g == 0 and b == 0: result = (result + cnt) % MOD print(result) if __name__ == "__main__": main()