結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
0