ABC281D - Max Multiple

考え方

dp[i][j][k] = i個目までみてj個和をとったときのk (mod D)の最大値．

回答例

dのループ範囲に注意．

N, K, D = map(int, input().split())
A = list(map(int, input().split()))

dp = [[[-1] * D for _ in range(K + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    a = A[i]
    for j in range(K + 1):
        for d in range(D):
            if dp[i][j][d] == -1: continue
            dp[i + 1][j][d] = max(dp[i + 1][j][d], dp[i][j][d])
            if j == K:continue
            dp[i + 1][j + 1][(d + a) % D] = max(dp[i + 1][j + 1][(d + a) % D], dp[i][j][d] + a)

print(dp[N][K][0])