前置き

間違ってても大目に見てくれや。

URL

問題文見ろ。

DはDPのD。 BIT全探索、next_combination()などに頼ると計算量に処される(自明)。

欲しいものはなんだろな?
A:「n番目までの要素から」「k個選んだとき」
=>dp[n][k]でヨシww!

Atcoder「WA」

余り、分かんないよね...
つまり
dp[n][k][d]:=n番目までの要素からk個選んだときの最大の和(ただし、d=和%mod D)

とりま全部-1。SにDの倍数が含まれへんっちゅうことやな。
dp[0][0][0]=0

A[n]を選ぶ場合と選ばない場合を考えないといけん。

dp[n+1][k+1][(d+A[n])%D]=max(dp[n+1][k+1][(d+A[n])%D],dp[n][k][d]+A[n])

dp[n+1][k][d]=max(dp[n+1][k][d],dp[n][k][d])

dp[n][k][d]==-1のときはそもそも考えなくてええんや。つーか考えんな。そもそも「解が存在しない」んやから選ぶとか選ぶ以前の問題やな。

答えはモロチンdp[N][K][0]。