Overview

In this problem, we choose whether or not to clear each of the \(N\) stages to maximize the sum of “the score \(A_i\) of each cleared stage” and “the bonus \(C\) for consecutive clears.” By focusing on whether the previous stage was cleared, we can solve this problem in \(O(N)\) time using dynamic programming (DP).

Analysis

Naive Approach

For each stage, there are \(2\) choices: “clear” or “do not clear.” Therefore, searching through all possible choices would result in \(2^N\) possibilities. Since \(N \le 10^6\), an exhaustive search will not finish within the time limit (resulting in TLE).

Key Insight to Solve the Problem

When deciding whether to clear stage \(i\), the only past information that affects the score is whether the previous stage \(i - 1\) was cleared. - If stage \(i - 1\) was not cleared: Clearing stage \(i\) yields a score of \(A_i\). - If stage \(i - 1\) was cleared: Clearing stage \(i\) yields a score of \(A_i + C\) (a combo bonus is awarded).

The choices made for stage \(i - 2\) and earlier do not directly affect whether the bonus is awarded at stage \(i\). Therefore, dynamic programming (DP), which sequentially records the maximum score up to stage \(i\) based on the previous state, is effective.

Algorithm

We define the DP states as follows:

• dp0: The maximum score when the current stage is not cleared
• dp1: The maximum score when the current stage is cleared

Each time we advance by \(1\) stage, we update the states as follows (let \(A\) be the score of the current stage):

1. When not clearing the next stage (next_dp0)

   • We can choose not to clear regardless of whether the previous stage was cleared or not. The score does not change.
   • next_dp0 = max(dp0, dp1)

2. When clearing the next stage (next_dp1)

   • If the previous stage was not cleared, the score increases by \(+A\) (dp0 + A).
   • If the previous stage was cleared, the bonus \(C\) is also awarded, so the score increases by \(+A + C\) (dp1 + A + C).
   • next_dp1 = max(dp0 + A, dp1 + A + C)

Initial Values and Answer

• At the start (considering stage \(0\) as completed):
  • State where nothing has been cleared: dp0 = 0
  • Since a cleared state does not exist yet, initialize it as an impossible state with a sufficiently small value (\(-\infty\)): dp1 = -INF
• After updating up to stage \(N\), max(dp0, dp1) gives the desired maximum score (this also properly accounts for the case where no stages are cleared, resulting in a score of \(0\)).

Complexity

• Time Complexity: \(O(N)\)
  • Transitions for each stage take \(O(1)\) time. Since there are \(N\) stages, the total time complexity is \(O(N)\), which easily passes within the time limit.
• Space Complexity: \(O(1)\)
  • By processing the input on the fly while only maintaining the previous states (dp0 and dp1), there is no need to store an extra array, requiring only \(O(1)\) space.

Implementation Notes

• Care with Integer Overflow:

  • The score \(A_i\) and bonus \(C\) can be up to \(10^9\), and since \(N = 10^6\), the maximum score can reach \(10^6 \times 2 \times 10^9 \approx 2 \times 10^{15}\).

  • This significantly exceeds the upper limit of a 32-bit signed integer (approximately \(2 \times 10^9\)), so make sure to use a 64-bit integer type (long long in C++).

  • For \(-\infty\) representing unreachable states, you also need to set a sufficiently small value (e.g., -\(4 \times 10^{18}\)) that does not cause overflow.

    Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long c;
    if (!(cin >> n >> c)) return 0;

    const long long INF = 4e18;
    long long dp0 = 0;
    long long dp1 = -INF;

    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        long long next_dp0 = max(dp0, dp1);
        long long next_dp1 = max(dp0 + a, dp1 + a + c);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }

    cout << max(dp0, dp1) << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.