結果

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

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    X = int(input[idx]); idx +=1
    Y = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    
    x_mod = X % K
    y_mod = Y % K
    a = min(x_mod, y_mod)
    b = max(x_mod, y_mod)
    
    # Initialize DP
    dp = [ [-1 for _ in range(K)] for _ in range(K) ]
    dp[a][b] = 0
    
    for num in A:
        c = num % K
        next_dp = [ [ -1 for _ in range(K)] for _ in range(K) ]
        
        for a_prev in range(K):
            for b_prev in range(a_prev, K):
                if dp[a_prev][b_prev] == -1:
                    continue
                
                sum_three = (a_prev + b_prev + c) % K
                points = dp[a_prev][b_prev]
                if sum_three == 0:
                    points += 1
                
                # Option 1: keep a_prev and b_prev
                new_a = a_prev
                new_b = b_prev
                if next_dp[new_a][new_b] < points:
                    next_dp[new_a][new_b] = points
                
                # Option 2: keep a_prev and c
                new_a2 = min(a_prev, c)
                new_b2 = max(a_prev, c)
                if next_dp[new_a2][new_b2] < points:
                    next_dp[new_a2][new_b2] = points
                
                # Option 3: keep b_prev and c
                new_a3 = min(b_prev, c)
                new_b3 = max(b_prev, c)
                if next_dp[new_a3][new_b3] < points:
                    next_dp[new_a3][new_b3] = points
        
        dp = next_dp
    
    max_points = -1
    for a_row in range(K):
        for b_col in range(a_row, K):
            if dp[a_row][b_col] > max_points:
                max_points = dp[a_row][b_col]
    
    print(max_points if max_points != -1 else 0)

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