結果

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

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    K = int(input[idx]); idx += 1
    X = int(input[idx]); idx += 1
    Y = int(input[idx]); idx += 1

    A = list(map(int, input[idx:idx+N]))
    idx += N

    c = [a % K for a in A]
    x_mod = X % K
    y_mod = Y % K

    current_dp = {(x_mod, y_mod): 0}

    for i in range(N):
        current_c = c[i]
        new_dp = {}
        for (a, b), points in current_dp.items():
            s = (a + b + current_c) % K
            new_points = points + (1 if s == 0 else 0)

            # Case 1: discard current_c, keep a and b
            key = (a, b)
            if key in new_dp:
                if new_dp[key] < new_points:
                    new_dp[key] = new_points
            else:
                new_dp[key] = new_points

            # Case 2: discard b, keep a and current_c
            key = (a, current_c)
            if key in new_dp:
                if new_dp[key] < new_points:
                    new_dp[key] = new_points
            else:
                new_dp[key] = new_points

            # Case 3: discard a, keep b and current_c
            key = (b, current_c)
            if key in new_dp:
                if new_dp[key] < new_points:
                    new_dp[key] = new_points
            else:
                new_dp[key] = new_points
        current_dp = new_dp

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

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