Overview

We want to maximize the final score under the condition that clearing two adjacent stages yields a bonus. This can be solved with dynamic programming (DP) where the state tracks whether the previous stage was cleared or not.

Analysis

Testing all combinations of “clearing or not clearing” each stage would result in \(2^N\) combinations. This will not run in time for \(N \le 10^6\).

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

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

• Clearing only stages \(1\) and \(3\) gives a score of \(3+3=6\).
• Clearing all stages gives a score of \(3-2+3+5 \times 2=14\).

Thus, we cannot make decisions based solely on individual stage scores.

The key observation here is that whether a combo bonus is awarded when clearing stage \(i\) depends only on whether stage \(i-1\) was cleared.

Therefore, we do not need to remember all previously cleared stages. It is sufficient to track the maximum score for both cases: “when the previous stage was not cleared” and “when the previous stage was cleared”.

Algorithm

Process the stages in order from stage \(1\). After processing up to stage \(i\), maintain the following two values:

• dp0: The maximum score from stages \(1\) to \(i\) when stage \(i\) is not cleared
• dp1: The maximum score from stages \(1\) to \(i\) when stage \(i\) is cleared

Initial Values

Before processing any stages, represent the initial state as follows:

• dp0 \(=0\)
• dp1 \(=-\infty\)

Since there is no previous stage that could have been cleared, set dp1 to a value small enough that it will never be chosen. In the code, \(-10^{30}\) is used.

Transitions

Let \(a\) be the score of the next stage to process.

1. When not clearing this stage

It does not matter whether the previous stage was cleared or not. Since neither score nor bonus is added:

\(\mathrm{next0}=\max(\mathrm{dp0},\mathrm{dp1})\)

2. When clearing this stage

We consider two cases based on the state of the previous stage:

• If the previous stage was not cleared: add \(a\) to dp0
• If the previous stage was cleared: add \(a+C\) to dp1

Therefore:

\(\mathrm{next1}=\max(\mathrm{dp0},\mathrm{dp1}+C)+a\)

We update dp0 and dp1 with these two values and proceed to the next stage.

Answer

Since the last stage may or may not be cleared, the answer is:

\(\max(\mathrm{dp0},\mathrm{dp1})\)

Each transition covers all cases of “whether the current stage is cleared” and “whether the previous stage was cleared”. Furthermore, for the same state, a choice with a higher accumulated score is always more advantageous going forward. Therefore, keeping only the maximum value for each state allows us to find the optimal solution.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) auxiliary space for the DP. However, since the provided code reads all inputs at once, it is \(O(N)\) including storing the input.

For each stage, we only perform a constant number of comparisons and additions.

Implementation Details

• Pay attention to the update order when using values before the transition.
  In the provided code, next0 is computed first, then dp1 is updated, and finally dp0 = next0. If dp0 were overwritten first, the previous value needed for updating dp1 would be lost.

• Represent impossible states with a sufficiently small value.
  If the initial value of dp1 were set to \(0\), it might erroneously grant a combo bonus to the very first stage. \(-10^{30}\) is sufficiently small relative to the range of scores in this problem.

• The score will not fit in a 32-bit integer.
  The maximum score can reach approximately \(2 \times 10^{15}\). While Python handles this natively, 64-bit integers are required in other languages.

• The option of clearing no stages at all is naturally included.
  Since dp0 is initialized to \(0\) and the option of not clearing stages is preserved at each step, the answer will never be negative.

  Source Code

import sys


def main():
    data = map(int, sys.stdin.buffer.read().split())
    n = next(data)
    c = next(data)

    dp0 = 0
    dp1 = -10**30

    for a in data:
        next0 = dp0 if dp0 > dp1 else dp1
        combo = dp1 + c
        dp1 = (dp0 if dp0 > combo else combo) + a
        dp0 = next0

    print(dp0 if dp0 > dp1 else dp1)


if __name__ == "__main__":
    main()

---

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