結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:43:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,757 bytes |
コンパイル時間 | 373 ms |
コンパイル使用メモリ | 81,908 KB |
実行使用メモリ | 293,068 KB |
最終ジャッジ日時 | 2025-06-12 18:43:37 |
合計ジャッジ時間 | 5,101 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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()) current = defaultdict(int) current[(0, 0, 0, 0, 0)] = 1 # (last_color, consecutive, r, g, b) for i in range(N): next_dp = defaultdict(int) for (last_color, consecutive, r, g, b), cnt in current.items(): # Try painting a color for color in [1, 2, 3]: if color == last_color: continue new_consecutive = consecutive + 1 if last_color != 0 else 1 if new_consecutive > 2: continue new_r = r + (1 if color == 1 else 0) new_g = g + (1 if color == 2 else 0) new_b = b + (1 if color == 3 else 0) if new_r > R or new_g > G or new_b > B: continue total_used = new_r + new_g + new_b if total_used > i + 1: continue key = (color, new_consecutive, new_r, new_g, new_b) next_dp[key] = (next_dp[key] + cnt) % MOD # Try leaving blank new_last_color = 0 new_consecutive = 0 new_r, new_g, new_b = r, g, b total_used = new_r + new_g + new_b if total_used > i + 1: continue key = (new_last_color, new_consecutive, new_r, new_g, new_b) next_dp[key] = (next_dp[key] + cnt) % MOD current = next_dp ans = 0 for (last_color, consecutive, r, g, b), cnt in current.items(): if r == R and g == G and b == B: ans = (ans + cnt) % MOD print(ans) if __name__ == "__main__": main()