結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:54:43 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,603 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 81,580 KB |
実行使用メモリ | 298,512 KB |
最終ジャッジ日時 | 2025-04-16 00:56:15 |
合計ジャッジ時間 | 3,750 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 = X % K y = Y % K a, b = sorted((x, y)) current_dp = defaultdict(int) current_dp[(a, b)] = 0 for a_i in A: c = a_i % K next_dp = defaultdict(int) for (a_prev, b_prev), points_prev in current_dp.items(): sum_three = (a_prev + b_prev + c) % K gain = 1 if sum_three == 0 else 0 new_points = points_prev + gain # Discard a_prev: new state is (b_prev, c) new_a, new_b = b_prev, c if new_a > new_b: new_a, new_b = new_b, new_a key = (new_a, new_b) if next_dp[key] < new_points: next_dp[key] = new_points # Discard b_prev: new state is (a_prev, c) new_a, new_b = a_prev, c if new_a > new_b: new_a, new_b = new_b, new_a key = (new_a, new_b) if next_dp[key] < new_points: next_dp[key] = new_points # Discard c: new state is (a_prev, b_prev) new_a, new_b = a_prev, b_prev if new_a > new_b: new_a, new_b = new_b, new_a key = (new_a, new_b) if next_dp[key] < new_points: next_dp[key] = new_points current_dp = next_dp print(max(current_dp.values()) if current_dp else 0) if __name__ == "__main__": main()