結果

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

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    X = int(data[idx])
    idx += 1
    Y = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+N]))
    
    x_mod = X % K
    y_mod = Y % K
    if x_mod > y_mod:
        x_mod, y_mod = y_mod, x_mod
    current_dp = {(x_mod, y_mod): 0}
    
    for a in A:
        c = a % K
        next_dp = defaultdict(int)
        for (a_prev, b_prev), points in current_dp.items():
            total = a_prev + b_prev + c
            new_points = points + (1 if total % K == 0 else 0)
            # Option 1: Keep a_prev and b_prev
            key = (a_prev, b_prev)
            if next_dp[key] < new_points:
                next_dp[key] = new_points
            # Option 2: Keep a_prev and c
            if a_prev <= c:
                key2 = (a_prev, c)
            else:
                key2 = (c, a_prev)
            if next_dp[key2] < new_points:
                next_dp[key2] = new_points
            # Option 3: Keep b_prev and c
            if b_prev <= c:
                key3 = (b_prev, c)
            else:
                key3 = (c, b_prev)
            if next_dp[key3] < new_points:
                next_dp[key3] = new_points
        current_dp = next_dp
    
    if current_dp:
        print(max(current_dp.values()))
    else:
        print(0)

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