コンテストページ: https://atcoder.jp/contests/abc281
コンテスト中AC: A〜D
コンテスト後にEをAC(自力)

D - Max Multiple

$N,K,D$ が小さい
倍数は $mod$ の情報があれば良い

これらからDPだろうと判断しました。
情報としては、

何項目までを考慮したか
選んだ項の総和の $mod\ D$
選んだ項の個数

が分かればよいので、

$dp[i][j][k]:=$ $A$ の $i$ 項目までを考慮し、選んだ項の総和の $mod\ D$ が $j$ であり、選んだ項の個数が $k$ であるときの選んだ項の総和の最大値

遷移は以下のとおりです。

$A_{i+1}$ を選ばない場合
$dp[i+1][j][k]\leftarrow max(dp[i+1][j][k], dp[i][j][k])$
$A_{i+1}$ を選ぶ場合
$dp[i+1][(j+A_i)\ mod\ D][k+1]\leftarrow max(dp[i][(j+A_i)\ mod\ D][k+1], dp[i][j][k]+A_i)$

初期値は、 $dp[0][0][0]\leftarrow 0$ としておき、その他は $-1$ などで埋めておけばよいです。

なお、 $dp[i][j][k]$ が $-1$ の場合は遷移元としないようにする必要があることに注意します。

答えは、 $dp[N][0][K]$ です。

提出コード: Submission #37160568 - AtCoder Beginner Contest 281

E - Least Elements

コンテスト中multisetで解こうとして結局だめでした。コンテスト後にWavelet Matrixで解けました。

$A_{i-M+1}$ から $A_i$ までを昇順に並べた数列を $B_i$ とします。 $B_i$ の先頭 $K$ 項の和を $S_i$ とします。

$i=M+1,M+2,\cdots ,N$ について、 $A_{i-M}$ を削除し、 $A_i$ を追加した場合に、 $B_{i-1}$ から $B_i$ にどのように変化したかがわかれば、 $S_{i-1}$ から変化分を増減させることで、 $S_i$ を計算できます。

これを考える時、 $A_{i-M},A_i$ がそれぞれ $B_{i-1},B_i$ の $K$ 番目以内かそうでないかの4通りを考えれば良いです。

具体的に説明します。

$A_{i-M}$ が $B_{i-1}$ の $K$ 番目以内
この時、 $A_{i-M}$ の分、和は減少します。
- $A_{i}$ が $B_i$ の $K$ 番目以内
  $A_{i-M}$ が削除され、 $A_i$ が挿入することを考えると、削除されて空いた箇所に左詰めまたは右詰めで各要素が移動し、 $A_i$ が挿入されたと考えることができます。
  このケースでは、新たに $A_i$ が $K$ 番目以内となってその分の和が増加するので、
  $S_i \leftarrow S_{i-1}-A_{i-M}+A_i$
  と計算できます。
- $A_{i}$ が $B_i$ の $K$ 番目より後ろ
  $A_{i-M}$ が削除されて空いた箇所にそれより後ろの要素が左詰めされて、 $A_i$ が挿入されます。
  このケースでは、 $B_{i-1}$ における $K+1$ 番目の要素が $B_i$ で新たに $K$ 番目となり、この分の和が増加するので、これを $B_{i,K+1}$ とおけば、
  $S_i \leftarrow S_{i-1}-A_{i-M}+B_{i,K+1}$
  と計算できます。
$A_{i-M}$ が $B_{i-1}$ の $K$ 番目より後ろ
このケースでは、 $A_{i-M}$ による和の減少はありません。
- $A_{i}$ が $B_i$ の $K$ 番目以内
  $A_i$ が挿入されると、 $A_{i-M}$ の削除によって空いた箇所に右詰めされるように動きます。このケースでは、新たに $A_i$ が $K$ 番目以内となってその分の和が増加し、 $B_{i-1}$ で $K$ 番目だった要素が $B_i$ における $K+1$ 番目となって、この分が減少するので、
  $S_i \leftarrow S_{i-1}+A_i-B_{i-1,K}$
  と計算できます。
- $A_{i}$ が $B_i$ の $K$ 番目より後ろ
  $A_i$ は和に影響しないので、 $S_i \leftarrow S_{i-1}$
  となります。

$B_i$ を全て記録することは $N^2$ の領域が必要となるので、不可能だと思います。また、仮にそれが可能だとしても、C++のvectorなら昇順ソートが毎回必要ですし、multisetでは何番目の要素かを得るのに時間がかかります。

そこで、Wavelet Matrixを使います。Wavelet Matrixは $O(NlogA_{max})$ で構築し、 $O(logA_{max})$ で指定区間の任意のx番目に小さい要素を得ることが可能です。(但し、 $A_{max}$ は $A$ に含まれる要素の最大値)
これで、 $O(NlogA_{max}+QlogA_{max})$ で解くことができます。