結果

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

ソースコード

diff # 

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_mod = X % K
    y_mod = Y % K
    a, b = sorted((x_mod, y_mod))
    current_dp = {(a, b): 0}
    
    for c_val in A:
        c = c_val % K
        next_dp = defaultdict(int)
        for (a_prev, b_prev), points in current_dp.items():
            sum_three = (a_prev + b_prev + c) % K
            add_point = 1 if sum_three == 0 else 0
            new_points = points + add_point
            
            # Discard a_prev
            new_a = min(b_prev, c)
            new_b = max(b_prev, c)
            if new_points > next_dp[(new_a, new_b)]:
                next_dp[(new_a, new_b)] = new_points
            
            # Discard b_prev
            new_a = min(a_prev, c)
            new_b = max(a_prev, c)
            if new_points > next_dp[(new_a, new_b)]:
                next_dp[(new_a, new_b)] = new_points
            
            # Discard c
            new_a = min(a_prev, b_prev)
            new_b = max(a_prev, b_prev)
            if new_points > next_dp[(new_a, new_b)]:
                next_dp[(new_a, new_b)] = new_points
        
        current_dp = dict(next_dp.items())
    
    if current_dp:
        print(max(current_dp.values()))
    else:
        print(0)

if __name__ == "__main__":
    main()
0