結果

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

ソースコード

diff #
raw source code 

def main():
    import sys
    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
    if x_mod > y_mod:
        x_mod, y_mod = y_mod, x_mod
    current = {(x_mod, y_mod): 0}
    
    c_mods = [a % K for a in A]
    
    for c_mod in c_mods:
        next_dict = {}
        for (a, b), score in current.items():
            s = (a + b + c_mod) % K
            d = 1 if s == 0 else 0
            
            # 保留a和c_mod
            new_a, new_b = a, c_mod
            if new_a > new_b:
                new_a, new_b = new_b, new_a
            key = (new_a, new_b)
            new_score = score + d
            if key in next_dict:
                if new_score > next_dict[key]:
                    next_dict[key] = new_score
            else:
                next_dict[key] = new_score
            
            # 保留b和c_mod
            new_a, new_b = b, c_mod
            if new_a > new_b:
                new_a, new_b = new_b, new_a
            key = (new_a, new_b)
            new_score = score + d
            if key in next_dict:
                if new_score > next_dict[key]:
                    next_dict[key] = new_score
            else:
                next_dict[key] = new_score
            
            # 保留a和b
            key = (a, b)
            new_score = score + d
            if key in next_dict:
                if new_score > next_dict[key]:
                    next_dict[key] = new_score
            else:
                next_dict[key] = new_score
        
        current = next_dict
    
    if not current:
        print(0)
    else:
        print(max(current.values()))
    
if __name__ == "__main__":
    main()
0