Codeforces 455A Boredom - Final Answer

$4.$ Determine the final answer

You process all values from $2$ up to $M$ using the formula $dp[i] = \max\bigl(dp[i - 1],\ dp[i - 2] + i \cdot \text{cnt}[i]\bigr), \quad \text{for } i = 2, 3, \dots, M.$

The final answer to the problem is simply $dp[M].$

This solution runs in $O(M)$ time and uses $O(M)$ space, where $M$ is the maximum value in the input. The structure is exactly the same as in the previous problems: define the state, find the transition, set the base cases, and read the final answer from the appropriate $dp$ state.