結果

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

ソースコード

diff #
raw source code 

import sys

def main():
    N, K, X, Y = map(int, sys.stdin.readline().split())
    X_mod = X % K
    Y_mod = Y % K
    current_dp = {}
    current_dp[(X_mod, Y_mod)] = 0
    A = list(map(int, sys.stdin.readline().split()))
    
    for card in A:
        c = card % K
        next_dp = {}
        
        # Case 3: discard the new card (c)
        for (a, b), score in current_dp.items():
            sum_abc = (a + b + c) % K
            new_score = score + (1 if sum_abc == 0 else 0)
            key = (a, b)
            if key in next_dp:
                if new_score > next_dp[key]:
                    next_dp[key] = new_score
            else:
                next_dp[key] = new_score
        
        # Case 1: discard a_prev, new state is (b_prev, c)
        group_by_x = {}
        for (a_prev, x), score in current_dp.items():
            if x not in group_by_x:
                group_by_x[x] = []
            group_by_x[x].append((a_prev, score))
        
        max_case1 = {}
        for x in group_by_x:
            max_val = -1
            a_special = (-x - c) % K
            max_special = -1
            for a, score in group_by_x[x]:
                current = score + (1 if (a + x + c) % K == 0 else 0)
                if current > max_val:
                    max_val = current
                if a == a_special:
                    special_score = score + 1
                    if special_score > max_special:
                        max_special = special_score
            max_case1[x] = max(max_val, max_special)
        
        for x in max_case1:
            key = (x, c)
            if key in next_dp:
                if max_case1[x] > next_dp[key]:
                    next_dp[key] = max_case1[x]
            else:
                next_dp[key] = max_case1[x]
        
        # Case 2: discard b_prev, new state is (a_prev, c)
        group_by_x2 = {}
        for (x, b_prev), score in current_dp.items():
            if x not in group_by_x2:
                group_by_x2[x] = []
            group_by_x2[x].append((b_prev, score))
        
        max_case2 = {}
        for x in group_by_x2:
            max_val = -1
            b_special = (-x - c) % K
            max_special = -1
            for b, score in group_by_x2[x]:
                current = score + (1 if (x + b + c) % K == 0 else 0)
                if current > max_val:
                    max_val = current
                if b == b_special:
                    special_score = score + 1
                    if special_score > max_special:
                        max_special = special_score
            max_case2[x] = max(max_val, max_special)
        
        for x in max_case2:
            key = (x, c)
            if key in next_dp:
                if max_case2[x] > next_dp[key]:
                    next_dp[key] = max_case2[x]
            else:
                next_dp[key] = max_case2[x]
        
        # Case 3 for (x, c) where previous state was (x, c)
        for (x, y), score in current_dp.items():
            if y == c:
                sum_abc = (x + y + c) % K
                new_score = score + (1 if sum_abc == 0 else 0)
                key = (x, y)
                if key in next_dp:
                    if new_score > next_dp[key]:
                        next_dp[key] = new_score
                else:
                    next_dp[key] = new_score
        
        current_dp = next_dp
    
    if not current_dp:
        print(0)
    else:
        print(max(current_dp.values()))

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