結果

問題 No.1515 Making Many Multiples
ユーザー lam6er
提出日時 2025-04-16 00:54:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,246 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 301,420 KB
最終ジャッジ日時 2025-04-16 00:56:22
合計ジャッジ時間 3,696 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    x0 = X % K
    y0 = Y % K
    A = list(map(int, sys.stdin.readline().split()))
    
    current = defaultdict(int)
    current[(x0, y0)] = 0
    
    for a in A:
        a_mod = a % K
        next_dp = defaultdict(int)
        for (a_prev, b_prev), score in current.items():
            sum_three = (a_prev + b_prev + a_mod) % K
            new_score = score + (1 if sum_three == 0 else 0)
            
            # Transition 1: discard a_prev → new state (b_prev, a_mod)
            key = (b_prev, a_mod)
            if next_dp[key] < new_score:
                next_dp[key] = new_score
            
            # Transition 2: discard b_prev → new state (a_prev, a_mod)
            key = (a_prev, a_mod)
            if next_dp[key] < new_score:
                next_dp[key] = new_score
            
            # Transition 3: discard a_mod → new state (a_prev, b_prev)
            key = (a_prev, b_prev)
            if next_dp[key] < new_score:
                next_dp[key] = new_score
        
        current = next_dp
    
    print(max(current.values()) if current else 0)

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