結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:33:46 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,295 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 406,836 KB |
最終ジャッジ日時 | 2025-03-20 20:35:05 |
合計ジャッジ時間 | 3,924 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 TLE * 1 -- * 25 |
ソースコード
N, K, X, Y = map(int, input().split()) A = list(map(int, input().split())) mod_A = [a % K for a in A] x = X % K y = Y % K p_initial = min(x, y) q_initial = max(x, y) INF = -1 << 60 current_dp = [[INF] * K for _ in range(K)] current_dp[p_initial][q_initial] = 0 current_states = [(p_initial, q_initial)] for c in mod_A: next_dp = [[INF] * K for _ in range(K)] next_states = set() for (p, q) in current_states: score = current_dp[p][q] sum_mod = (p + q + c) % K add = 1 if sum_mod == 0 else 0 new_score = score + add if next_dp[p][q] < new_score: next_dp[p][q] = new_score next_states.add((p, q)) new_p, new_q = min(p, c), max(p, c) if next_dp[new_p][new_q] < new_score: next_dp[new_p][new_q] = new_score next_states.add((new_p, new_q)) new_p2, new_q2 = min(q, c), max(q, c) if next_dp[new_p2][new_q2] < new_score: next_dp[new_p2][new_q2] = new_score next_states.add((new_p2, new_q2)) current_dp = [row[:] for row in next_dp] current_states = list(next_states) max_score = 0 for p in range(K): for q in range(p, K): if current_dp[p][q] > max_score: max_score = current_dp[p][q] print(max_score)