結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:10:26 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,599 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 277,876 KB |
最終ジャッジ日時 | 2025-04-16 00:11:50 |
合計ジャッジ時間 | 5,135 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 7 TLE * 1 -- * 6 |
ソースコード
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)