結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:29:22 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,712 bytes |
コンパイル時間 | 681 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 223,052 KB |
最終ジャッジ日時 | 2025-06-12 13:34:25 |
合計ジャッジ時間 | 5,142 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 7 TLE * 1 -- * 6 |
ソースコード
MOD = 10**9 + 7 N, R, G, B = map(int, input().split()) from collections import defaultdict prev_dp = defaultdict(int) prev_dp[(0, 0, 0, 0, 0)] = 1 # (prev_color, clen, r, g, b) for _ in range(N): current_dp = defaultdict(int) for (prev_color, clen, r, g, b), cnt in prev_dp.items(): # Option 1: Do not paint this column new_clen = 0 new_state = (0, new_clen, r, g, b) current_dp[new_state] = (current_dp[new_state] + cnt) % MOD # Option 2: Paint this column with a color different from previous for color in [1, 2, 3]: # 1: Red, 2: Green, 3: Blue if color == prev_color: continue # Same color as previous is not allowed # Check consecutive length constraint if prev_color != 0: # Previous column was painted new_clen_p = clen + 1 if new_clen_p > 2: continue # Exceeds maximum consecutive allowed else: new_clen_p = 1 # Start new consecutive # Update color 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 # Exceeds required counts new_state = (color, new_clen_p, nr, ng, nb) current_dp[new_state] = (current_dp[new_state] + cnt) % MOD prev_dp = current_dp # Sum all states where r=R, g=G, b=B result = 0 for (pc, clen, r, g, b), cnt in prev_dp.items(): if r == R and g == G and b == B: result = (result + cnt) % MOD print(result)