Overview

In this problem, for each of the \(N\) stages, we choose whether or not to clear it, aiming to maximize the total score consisting of clear rewards \(A_i\) and combo bonuses \(C\) for consecutive clears. We can solve this in \(O(N)\) time using dynamic programming (DP), where the state represents whether the immediately preceding stage was cleared.

Analysis

Naive Approach and Its Limitations

Since there are 2 choices for each stage—”clear” or “do not clear”—an exhaustive search testing all combinations would require checking \(2^N\) possibilities. Since the constraint is \(N \le 10^6\), an exhaustive search will easily exceed the time limit (TLE).

Furthermore, a simple greedy approach such as “only clear stages where \(A_i > 0\)” is also incorrect. For example, even if \(A_i\) is negative, clearing it along with adjacent stages can yield the bonus \(C\), making the net change positive overall.

Reduction to Dynamic Programming

Whether the bonus \(C\) is earned upon clearing stage \(i\) depends solely on whether the immediately preceding stage \(i - 1\) was cleared. The choices made for earlier stages (stage \(i - 2\) and before) have no impact on the score obtained at stage \(i\).

In problems like this, where we only need the immediately preceding state rather than the full history, dynamic programming (DP) is effective. By iterating through the stages from left to right, we can find the optimal solution by maintaining only the state of “whether the previous stage was cleared.”

Algorithm

We define the DP states as follows:

• \(dp_0\): The maximum score when the current stage is not cleared
• \(dp_1\): The maximum score when the current stage is cleared

When processing stage \(i\) with score \(A_i\), the transitions to the next stage’s states are updated as follows:

1. When stage \(i\) is not cleared (\(ndp_0\)):

   • It does not matter whether the previous stage \(i - 1\) was cleared or not. Since no bonus is earned, we simply inherit the maximum value from the previous step. $\(ndp_0 = \max(dp_0, dp_1)\)$

2. When stage \(i\) is cleared (\(ndp_1\)):

   • If the previous stage was not cleared: \(A_i\) is added to the previous score \(dp_0\).
   • If the previous stage was cleared: both \(A_i\) and the combo bonus \(C\) are added to the previous score \(dp_1\).
   • We take the maximum of these two values. $\(ndp_1 = \max(dp_0 + A_i, \; dp_1 + A_i + C)\)$

Initial and Final States

• Before starting the game (at stage \(0\)):
  • Since nothing has been cleared yet, \(dp_0 = 0\).
  • The state “the previous stage was cleared” is impossible, so \(dp_1 = -\infty\) (a sufficiently small value).
• After processing all stages, the maximum final score is \(\max(dp_0, dp_1)\).

Complexity

• Time Complexity: \(O(N)\)
  • We iterate through the stages \(N\) times, performing only a constant number of additions and comparisons in each step, resulting in \(O(N)\) overall. This runs well within the time limit (2 seconds) even for \(N = 10^6\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input array. Since updating the DP states only requires maintaining the previous two values, the space complexity for the DP table itself is \(O(1)\).

Implementation Points

• Setting the Initial Value \(-\infty\): The values of \(A_i\) can be as small as \(-10^9\), and accumulating them can result in very large negative numbers. Therefore, for initial values representing unreachable/impossible states, choose a sufficiently large negative number in magnitude such as \(-10^{18}\) so that it is never mistakenly chosen as an optimal value.

• Fast I/O: In Python, reading \(N = 10^6\) inputs line by line incurs significant overhead, so using methods like sys.stdin.read().split() to read all inputs at once helps speed up execution.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = int(input_data[1])
    A = [int(x) for x in input_data[2:]]
    
    dp0 = 0
    dp1 = -10**18
    
    for a in A:
        ndp0 = dp0 if dp0 > dp1 else dp1
        v1 = dp0 + a
        v2 = dp1 + a + C
        ndp1 = v1 if v1 > v2 else v2
        dp0, dp1 = ndp0, ndp1
        
    print(dp0 if dp0 > dp1 else dp1)

if __name__ == '__main__':
    main()

---

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