結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:10:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,317 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 274,684 KB
最終ジャッジ日時 2025-06-12 13:13:28
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, k, x, y = map(int, input().split())
a_list = list(map(int, input().split()))

x_mod = x % k
y_mod = y % k
initial_r, initial_s = sorted((x_mod, y_mod))

prev_dp = {}
prev_dp[(initial_r, initial_s)] = 0

for a in a_list:
    a_mod = a % k
    curr_dp = {}
    for (r, s), points in prev_dp.items():
        sum_mod = (r + s + a_mod) % k
        new_points = points + (1 if sum_mod == 0 else 0)
        
        # Transition 1: discard a_mod, keep r and s
        key = (r, s)
        if key in curr_dp:
            if new_points > curr_dp[key]:
                curr_dp[key] = new_points
        else:
            curr_dp[key] = new_points
        
        # Transition 2: discard s, keep r and a_mod
        new_r, new_s = sorted((r, a_mod))
        key = (new_r, new_s)
        if key in curr_dp:
            if new_points > curr_dp[key]:
                curr_dp[key] = new_points
        else:
            curr_dp[key] = new_points
        
        # Transition 3: discard r, keep s and a_mod
        new_r, new_s = sorted((s, a_mod))
        key = (new_r, new_s)
        if key in curr_dp:
            if new_points > curr_dp[key]:
                curr_dp[key] = new_points
        else:
            curr_dp[key] = new_points
    prev_dp = curr_dp

if prev_dp:
    print(max(prev_dp.values()))
else:
    print(0)
0