Observe that the final marks should be a non-decreasing sequence. (The observation was not true for the original problem, which was incorrect as a result.) This is because it never hurts Bob to swap marks ~m_i~ and ~m_j~ if ~m_i>m_j~ and ~i<j~, since the ~v~ array is non-decreasing.

With this observation, a dynamic programming solution can be found for the first subtask. Let ~dp[i][j][e]~ be the most amount of money given that only the first ~i~ tests are being considered, ~m_i = j~, and ~e = m_1 + m_2 + \dots + m_i~. Then the transition can be done in ~\mathcal{O}(N)~ by considering the length of marks equal to exactly ~j~. The rest of the marks will definitely be less than ~m_i~ and will contribute to the money earned.

Time Complexity: ~\mathcal{O}(N^3E)~

For the second subtask, a similar approach is used. Instead of considering the tests from ~1~ to ~N~, this dynamic programming solution considers the tests from ~N~ to ~1~. The advantage here is the dimension ~[j]~ in the first subtask is no longer necessary, as ~m_i~ should always be equal to ~0~. So let ~dp[i][e]~ be the most amount of money given that only the last ~N-i+1~ tests are being considered and ~e = m_i + m_{i+1} + \dots + m_N~. If ~m_i = m_j < m_{j+1}~, that is equivalent to adding ~1~ to all the marks in the transition. So

$$\displaystyle dp[i][e] = \min_{j>i} dp[j+1][e-(N-j)] + (j-i+1) \cdot (v_j + v_{j+1} + \dots + v_N)$$

Then the transition can be done in ~\mathcal{O}(N)~.

Time Complexity: ~\mathcal{O}(N^2E)~

For the final subtask, note that the convex hull optimization can be applied to the dynamic programming solution from the second subtask. This changes the transition into amortized ~\mathcal{O}(1)~.

Time Complexity: ~\mathcal{O}(NE)~