結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:54:48 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,188 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 319,780 KB |
最終ジャッジ日時 | 2025-04-16 00:56:21 |
合計ジャッジ時間 | 3,694 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 TLE * 1 -- * 25 |
ソースコード
import sys from collections import defaultdict def main(): N, K, X, Y = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) X_mod = X % K Y_mod = Y % K A_mod = [a % K for a in A] prev_dp = defaultdict(int) prev_dp[(X_mod, Y_mod)] = 0 for c in A_mod: curr_dp = defaultdict(int) for (a, b), score in prev_dp.items(): sum_three = (a + b + c) % K new_score = score + (1 if sum_three == 0 else 0) # Discard a: new state (b, c) key = (b, c) if curr_dp.get(key, -1) < new_score: curr_dp[key] = new_score # Discard b: new state (a, c) key = (a, c) if curr_dp.get(key, -1) < new_score: curr_dp[key] = new_score # Discard c: new state (a, b) key = (a, b) if curr_dp.get(key, -1) < new_score: curr_dp[key] = new_score prev_dp = curr_dp if not prev_dp: print(0) else: print(max(prev_dp.values())) if __name__ == "__main__": main()