Overview

In this problem, you can freely choose whether to “clear” or “skip” each stage. You receive the sum of \(A_i\) for all chosen stages plus “the number of times two adjacent stages are both chosen \(\times C\)”. The goal is to find the maximum possible final score. This can be solved with a typical “selection problem with adjacent dependencies (not an interval DP)” = a 1D DP with 2 states (1-bit DP).

Analysis

Naive Approach

Trying all combinations of stages to clear results in \(2^N\) possibilities, which is far too slow for \(N \le 10^6\).

Greedy Does Not Work

One might be tempted to think, “we should just clear the stages where \(A_i > 0\),” but this is incorrect. For example:

• \(N = 3,\ C = 4,\ A = (10, -5, 10)\)

In this case, choosing only stages with positive \(A_i\) (stages \(1\) and \(3\)) yields no bonus, giving a score of \(20\). However, clearing all stages gives \(10 - 5 + 10 + 2 \times 4 = 23\), which is strictly better. In other words, it can be advantageous to select an otherwise disadvantageous stage in order to connect both neighbors and receive the bonus twice.

Conversely:

• \(N = 3,\ C = 4,\ A = (-5, 10, -5)\)

Here, clearing all stages gives \(8\), whereas clearing only stage \(2\) gives \(10\), so it is sometimes better not to connect them. Therefore, decisions cannot be made solely based on the sign of the current stage; we need to carry information forward from the left.

Key Observation

Looking at the contributions to the score, there are only:

• \(A_i\) from stage \(i\) itself
• Bonus \(C\), which occurs depending on whether the immediately preceding stage \(i-1\) was cleared

Thus, when processing stage \(i\), the only information we need to keep track of is a single bit of state: “whether the previous stage was cleared or not”. Dynamic programming naturally follows from this observation.

Algorithm

\(dp[i][0]\): Maximum score after considering stages \(1 \dots i\), where stage \(i\) is not cleared
\(dp[i][1]\): Maximum score after considering stages \(1 \dots i\), where stage \(i\) is cleared

As the base case, we introduce a dummy “stage \(0\)”: $\(dp[0][0] = 0,\qquad dp[0][1] = -\infty\)\( (Since stage \)0$ does not actually exist, the cleared state is invalid/prohibited).

The transitions are as follows:

• If stage \(i\) is cleared:
  • Previous stage was not cleared \(\to\) no bonus: \(dp[i-1][0] + A_i\)
  • Previous stage was also cleared \(\to\) receives bonus \(C\): \(dp[i-1][1] + C + A_i\) $\(dp[i][1] = \max(dp[i-1][0],\ dp[i-1][1] + C) + A_i\)$
• If stage \(i\) is not cleared (no bonus is awarded): $\(dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1])\)$

The answer is \(\max(dp[N][0], dp[N][1])\). Since we initialize \(dp[0][0]=0\), the choice of “clearing no stages at all (score \(0\))” is naturally included as a candidate.

Concrete Example (\(N=3, C=4, A=(10,-5,10)\))

\(i\)	\(dp[i][0]\)	\(dp[i][1]\)
0	0	\(-\infty\)
1	0	\(0 + 10 = 10\)
2	\(\max(0,10)=10\)	\(\max(0,\ 10+4) - 5 = 9\)
3	\(\max(10,9)=10\)	\(\max(10,\ 9+4) + 10 = 23\)

The answer is correctly obtained as \(\max(10, 23) = 23\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (or \(O(N)\) if storing the input array)

Since \(dp[i][\cdot]\) only depends on \(dp[i-1][\cdot]\), it suffices to simply overwrite two variables (dp0, dp1).

Implementation Notes

• Use 2 variables instead of allocating arrays: For \(N = 10^6\), allocating two DP tables of length \(N\) in Python is costly in terms of both memory and execution time. Simply update dp0 and dp1. When updating, make sure to store new values in temporary variables before assigning them so that the values from \(dp[i-1]\) are not overwritten prematurely.

• Fast I/O: Read the entire input at once using sys.stdin.buffer.read().split(), and convert elements via int() only as needed. Calling input() \(10^6\) times is critically slow. In the code above, we iterate through data[2], data[3], \dots while converting them to int on the fly.

• Use conditional expressions instead of max(): Because built-in function calls have non-negligible overhead in Python, using conditional expressions like a if a > b else b can speed up execution (which makes a significant difference across \(10^6\) iterations).

• Overflow / Initial values: The score can reach approximately \(10^6 \times 10^9 \times 2 = 2 \times 10^{15}\), so using 64-bit integers (long long in C++, etc.) is mandatory. Python supports arbitrary-precision integers, so overflow is not an issue. However, using float('-inf') for \(-\infty\) introduces floating-point values into the arithmetic; it is safer to either convert the output via int() (as in the code) or use a sufficiently small integer like -10**18 from the start.

• Edge cases such as \(C = 0\) or \(N = 1\) (\(dp[1][1] = A_1\), giving the answer \(\max(0, A_1)\)) are handled correctly by this DP without any special branching.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    c = int(data[1])
    NEG = float('-inf')
    dp0 = 0
    dp1 = NEG
    for i in range(2, n + 2):
        a = int(data[i])
        t = dp1 + c
        nd1 = (dp0 if dp0 > t else t) + a
        nd0 = dp0 if dp0 > dp1 else dp1
        dp0 = nd0
        dp1 = nd1
    ans = dp0 if dp0 > dp1 else dp1
    sys.stdout.write(str(int(ans)) + "\n")

main()

---

This editorial was generated by claude5opus-high.