Overview

We choose whether or not to clear each stage to maximize the sum of stage scores and combo bonuses between adjacent stages. This can be solved with dynamic programming where the state is “whether the immediately preceding stage was cleared.”

Analysis

For each stage, there are \(2\) choices: “clear” or “do not clear.” Checking all combinations would require examining \(2^N\) possibilities, which will not finish in time for \(N \le 10^6\).

Furthermore, simply clearing only the stages where \(A_i\) is positive is not correct. Even for a stage with a negative score, clearing it might be advantageous due to the combo bonus.

For example, consider the case where \(C=5\) and \(A=(3,-2,3)\).

• If we clear only stages \(1,3\), the score is \(3+3=6\).
• If we clear all stages, the score is \(3-2+3+5+5=14\).

Thus, decisions cannot be made based on individual stage scores alone.

Here, when clearing stage \(i\), the only bonus that can newly arise is for the pair \((i-1,i)\). Therefore, as long as we know whether the immediately preceding stage was cleared, we do not need to keep track of the detailed choices made prior to that.

If the state of the immediately preceding stage is the same, any future increase in score will also be the same, so we only need to retain the maximum score achieved up to that point.

Algorithm

We process the stages from left to right and maintain the following \(2\) values:

• skip: the maximum score when the last processed stage is not cleared
• take: the maximum score when the last processed stage is cleared

1. Initialization

Before processing any stages, we set:

• skip \(=0\)
• take \(=-\infty\)

The score when nothing has been cleared is \(0\). On the other hand, since the state “the immediately preceding stage was cleared” does not exist yet, we initialize take to a sufficiently small value.

2. Transitions for Each Stage

Let \(A_i\) be the score of stage \(i\).

If stage \(i\) is not cleared:

Regardless of whether the previous stage was cleared, neither the score nor the bonus increases. Therefore:

\(\mathrm{next\_skip}=\max(\mathrm{skip},\mathrm{take})\)

If stage \(i\) is cleared:

Depending on the choice made for the previous stage, there are \(2\) cases:

• The previous stage was not cleared: add \(A_i\) to skip
• The previous stage was cleared: add \(A_i+C\) to take

Therefore:

\(\mathrm{next\_take}=\max(\mathrm{skip},\mathrm{take}+C)+A_i\)

After computing these two values, update skip and take accordingly.

3. Answer

After processing all stages, output the maximum value between clearing and not clearing the last stage:

\(\mathrm{answer}=\max(\mathrm{skip},\mathrm{take})\)

Each transition accounts for all combinations of whether the current stage is cleared and whether the previous stage was cleared. Consequently, the maximum score for each state is correctly maintained, yielding the overall maximum score at the end.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

Each stage is processed once. Since we can update values on the fly while reading the input, there is no need to store the array \(A\).

Implementation Notes

• Use 64-bit integers for scores.
  The score can reach up to around \(N\cdot 10^9+(N-1)\cdot 10^9\), which does not fit in a 32-bit integer. Use long long in the implementation.

• Use a sufficiently small value for impossible states.
  In the code, -(1LL << 60) is used instead of \(-\infty\). It is sufficiently smaller than any possible score within the constraints, and will not underflow or overflow when scores or bonuses are added.

• Compute both next states using the values before updating.
  If you overwrite skip first, the calculation of next_take will erroneously use the updated value. Be sure to compute both next_skip and next_take before assigning them.

• The option of clearing nothing is naturally handled.
  Since skip is initialized to \(0\) and we can continue choosing not to clear any stages, the answer will never be negative.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long C;
    cin >> N >> C;

    long long skip = 0;
    long long take = -(1LL << 60);

    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;

        long long next_skip = max(skip, take);
        long long next_take = max(skip, take + C) + A;

        skip = next_skip;
        take = next_take;
    }

    cout << max(skip, take) << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.