\(d[j][c]\) を「所持金が最初 \(c\) 円で、\(i=j,j+1,\ldots,N\) の順に所持金が \(A_i\) 円以上なら品物 \(i\) を買う行動を繰り返した時の最終的な購入金額の合計」と定義します。\(d[1][0],d[1][1],\ldots,d[1][M]\) の値が求まれば良いです。

この DP には以下のような漸化式が成り立ちます。

\[ d[i][c]= \begin{cases} d[i+1][c-A_i]+A_i & (c \geq A_i) \\ d[i+1][c] & (c < A_i) \end{cases} \]

この漸化式から、\(d[1][0],d[1][1],\ldots,d[1][M]\) の値を全て求めるためには \(d[2][0],d[2][1],\ldots,d[2][\max(A_1 - 1,M-A_1)]\) を全て求める必要があります。同様に考えていくことで、\(C_1=M,C_{i+1}=\min(C_i,\max(A_i-1,C_i-A_i))\) で定義される \(C=(C_1,C_2,\ldots,C_{N+1})\) に対し \(d[i][*]\) で必要な値は \(d[i][0],d[i][1],\ldots,d[i][C_i]\) であることが分かります。

次に、\(d[j]\) を逆順に復元していくことを考えます。この DP の遷移を愚直に辿ると計算量が \(O(NM)\) となり間に合わないので、より高速に計算する方法を考えます。

\(D[i]=(d[i][0],d[j][1],\ldots,d[j][C_j])\) とします。初期値は \(D[N+1]=(0,0,\ldots,0)\) です。

\(A_i - 1 > C_i - A_i\) のとき、\(D[i]\) は \(D[i+1]\) の末尾に \((d[i+1][0]+A_i,d[i+1][1]+A_i,\ldots,d[i+1][C_i-A_i]+A_i)\) を連結して作ることができます。

また、\(A_i - 1 \le C_i-A_i\) のとき \(D[i]\) は \((d[i+1][0]-A_i,d[i+1][1]-A_i,\ldots,d[i+1][A_i-1]-A_i)\) と \(D[i+1]\) を連結した後に全ての要素に \(A_i\) を足して作ることができます。

全ての要素に \(A_i\) を足す操作を毎回行わずに offset として保持しておくことで、これらの操作は \(N\) 回まとめて合計で \(O(N+M)\) で実行することができます。

これらの操作は deque などを用いることで簡単に実装することができます。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N+M)\) です。

原案：nok0