Define \(d[j][c]\) as “the total purchase amount when starting with \(c\) yen and performing the action of buying item \(i\) if the current money is at least \(A_i\) yen, for \(i=j,j+1,\ldots,N\) in order.” It suffices to find the values of \(d[1][0],d[1][1],\ldots,d[1][M]\).

The following recurrence holds for this 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} \]

From this recurrence, to compute all of \(d[1][0],d[1][1],\ldots,d[1][M]\), we need all of \(d[2][0],d[2][1],\ldots,d[2][\max(A_1 - 1,M-A_1)]\). By reasoning similarly, defining \(C=(C_1,C_2,\ldots,C_{N+1})\) by \(C_1=M,C_{i+1}=\min(C_i,\max(A_i-1,C_i-A_i))\), the values of \(d[i][*]\) that are needed are \(d[i][0],d[i][1],\ldots,d[i][C_i]\).

Next, consider recovering \(d[j]\) in reverse order. Naively following the transitions of this DP would result in a time complexity of \(O(NM)\), which is too slow, so we consider a faster method.

Let \(D[i]=(d[i][0],d[i][1],\ldots,d[i][C_i])\). The initial value is \(D[N+1]=(0,0,\ldots,0)\).

When \(A_i - 1 > C_i - A_i\), \(D[i]\) can be formed by concatenating \((d[i+1][0]+A_i,d[i+1][1]+A_i,\ldots,d[i+1][C_i-A_i]+A_i)\) to the end of \(D[i+1]\).

When \(A_i - 1 \le C_i-A_i\), \(D[i]\) can be formed by concatenating \((d[i+1][0]-A_i,d[i+1][1]-A_i,\ldots,d[i+1][A_i-1]-A_i)\) and \(D[i+1]\), then adding \(A_i\) to all elements.

By maintaining the operation of adding \(A_i\) to all elements as an offset rather than performing it each time, these operations can be executed in \(O(N+M)\) in total over the \(N\) steps.

These operations can be implemented easily using a deque or similar data structure.

By implementing the above appropriately, this problem can be solved. The time complexity is \(O(N+M)\) per test case.

Proposed by: nok0