結果

問題 No.1515 Making Many Multiples
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:56:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,712 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 81,840 KB
実行使用メモリ 65,384 KB
最終ジャッジ日時 2025-04-16 00:58:07
合計ジャッジ時間 4,088 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr += 1
    K = int(input[ptr]); ptr += 1
    X = int(input[ptr]); ptr += 1
    Y = int(input[ptr]); ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    x = X % K
    y = Y % K
    a, b = sorted((x, y))

    current_dp = [[-1] * K for _ in range(K)]
    current_dp[a][b] = 0

    for card in A:
        c = card % K
        next_dp = [[-1] * K for _ in range(K)]
        for a_prev in range(K):
            for b_prev in range(a_prev, K):
                if current_dp[a_prev][b_prev] == -1:
                    continue
                current_score = current_dp[a_prev][b_prev]
                sum_three = (a_prev + b_prev + c) % K
                new_score = current_score + (1 if sum_three == 0 else 0)

                # Discard a_prev
                new_a = min(b_prev, c)
                new_b = max(b_prev, c)
                if next_dp[new_a][new_b] < new_score:
                    next_dp[new_a][new_b] = new_score

                # Discard b_prev
                new_a = min(a_prev, c)
                new_b = max(a_prev, c)
                if next_dp[new_a][new_b] < new_score:
                    next_dp[new_a][new_b] = new_score

                # Discard c
                new_a = a_prev
                new_b = b_prev
                if next_dp[new_a][new_b] < new_score:
                    next_dp[new_a][new_b] = new_score

        current_dp = next_dp

    max_score = 0
    for a in range(K):
        for b in range(a, K):
            if current_dp[a][b] > max_score:
                max_score = current_dp[a][b]
    print(max_score)

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