結果

問題 No.1515 Making Many Multiples
ユーザー lam6er
提出日時 2025-03-31 17:40:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,397 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 72,192 KB
最終ジャッジ日時 2025-03-31 17:42:10
合計ジャッジ時間 4,251 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

x_mod = x % k
y_mod = y % k
initial_pair = tuple(sorted((x_mod, y_mod)))
current_dp = {initial_pair: 0}

a_mod = [a % k for a in a_list]

for c in a_mod:
    next_dp = {}
    for (a_prev, b_prev), score in current_dp.items():
        sum_ab = (a_prev + b_prev) % k
        current_point = 1 if (sum_ab + c) % k == 0 else 0
        new_score = score + current_point
        
        # Discard a_prev: new pair is (b_prev, c)
        new_pair = tuple(sorted((b_prev, c)))
        if new_pair in next_dp:
            if next_dp[new_pair] < new_score:
                next_dp[new_pair] = new_score
        else:
            next_dp[new_pair] = new_score
        
        # Discard b_prev: new pair is (a_prev, c)
        new_pair = tuple(sorted((a_prev, c)))
        if new_pair in next_dp:
            if next_dp[new_pair] < new_score:
                next_dp[new_pair] = new_score
        else:
            next_dp[new_pair] = new_score
        
        # Discard c: keep the previous pair (a_prev, b_prev)
        new_pair = (a_prev, b_prev)
        if new_pair in next_dp:
            if next_dp[new_pair] < new_score:
                next_dp[new_pair] = new_score
        else:
            next_dp[new_pair] = new_score
    current_dp = next_dp

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