結果

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

ソースコード

diff # 

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
    s = min(x_mod, y_mod)
    t = max(x_mod, y_mod)
    
    INF = -10**18
    prev_dp = [ [INF for _ in range(K)] for __ in range(K) ]
    prev_dp[s][t] = 0
    
    for a in A:
        c = a % K
        curr_dp = [ [INF for _ in range(K)] for __ in range(K) ]
        for s_prev in range(K):
            for t_prev in range(s_prev, K):
                if prev_dp[s_prev][t_prev] == INF:
                    continue
                sum_mod = (s_prev + t_prev + c) % K
                points = 1 if sum_mod == 0 else 0
                
                # Option 1: discard s_prev, keep t_prev and c
                new_s1 = t_prev
                new_t1 = c
                if new_s1 > new_t1:
                    new_s1, new_t1 = new_t1, new_s1
                if curr_dp[new_s1][new_t1] < prev_dp[s_prev][t_prev] + points:
                    curr_dp[new_s1][new_t1] = prev_dp[s_prev][t_prev] + points
                
                # Option 2: discard t_prev, keep s_prev and c
                new_s2 = s_prev
                new_t2 = c
                if new_s2 > new_t2:
                    new_s2, new_t2 = new_t2, new_s2
                if curr_dp[new_s2][new_t2] < prev_dp[s_prev][t_prev] + points:
                    curr_dp[new_s2][new_t2] = prev_dp[s_prev][t_prev] + points
                
                # Option3: discard c, keep s_prev and t_prev
                new_s3 = s_prev
                new_t3 = t_prev
                if curr_dp[new_s3][new_t3] < prev_dp[s_prev][t_prev] + points:
                    curr_dp[new_s3][new_t3] = prev_dp[s_prev][t_prev] + points
        prev_dp = curr_dp
    
    max_points = max([max(row) for row in prev_dp])
    print(max_points)

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