Overview

In this problem, we choose an arbitrary subset of \(N\) stages to maximize the sum of \(A_i\) of the chosen stages plus the number of adjacent chosen pairs \(\times C\). It can be solved using a simple linear DP (similar to bitmask DP on a single state) that maintains whether the immediately preceding stage was chosen or not.

Analysis

Issues with the Naive Approach

Trying all possible subsets of cleared stages gives \(2^N\) combinations. Since \(N \le 10^6\), this will naturally result in Time Limit Exceeded (TLE).

Does a Greedy Approach Work?

A greedy strategy like “only choose stages with \(A_i > 0\)” is incorrect. For example:

N=3, C=10
A = 5, -3, 5

If we only choose the stages with \(A_i > 0\), the score is \(5+5=10\). However, if we also choose stage \(2\), the score becomes \(5-3+5+2\times 10 = 27\). It is better to pick the negative stage as a “bridge”. Conversely, if \(C=0\), there is no reason to pick a negative stage. In other words, we cannot decide based on the score of a single stage in isolation; the essence of this problem is that the decision depends on whether the adjacent stages are chosen.

Key Observation

Focus on the incremental change in score. When we choose stage \(i\), the score increases by only:

• \(A_i\) (always)
• an additional \(C\), if stage \(i-1\) was also chosen

In other words, as long as we know whether the immediately preceding stage was chosen or not, the score contribution of the current stage is uniquely determined. We do not need any information about stages before that.

Therefore, we can use a dynamic programming approach that decides sequentially from the beginning, where the state only needs 2 values: “the previous stage was chosen” or “the previous stage was not chosen”.

Algorithm

We maintain the following two values after processing up to the \(i\)-th stage:

• \(dp[i][0]\): the maximum score obtainable from stages \(1..i\) if stage \(i\) is not chosen
• \(dp[i][1]\): the maximum score obtainable from stages \(1..i\) if stage \(i\) is chosen

The transitions are as follows:

• \(dp[i][0] = \max(dp[i-1][0],\; dp[i-1][1])\)
  • Since stage \(i\) is not chosen, the score does not increase and no bonus is granted. The previous stage could either be chosen or not.
• \(dp[i][1] = \max(dp[i-1][0],\; dp[i-1][1] + C) + A_i\)
  • Since stage \(i\) is chosen, \(A_i\) is added. Additionally, the bonus \(C\) is awarded only if the previous stage was also chosen.

For the base cases (the state before processing any stages), set \(dp[0][0]=0\) and \(dp[0][1]=-\infty\) (stage 0 does not exist, so being “chosen” is impossible).

The final answer is \(\max(dp[N][0], dp[N][1])\).

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

\(i\)	\(A_i\)	\(dp[i][0]\)	\(dp[i][1]\)
0	-	0	\(-\infty\)
1	5	0	\(\max(0,-\infty)+5=5\)
2	-3	\(\max(0,5)=5\)	\(\max(0,5+10)-3=12\)
3	5	\(\max(5,12)=12\)	\(\max(5,12+10)+5=27\)

The answer is \(\max(12,27)=27\), which matches our earlier analysis.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) (if we reuse just the two values from the previous step without allocating a full DP array. If the input is stored in an array, it is \(O(N)\))

Implementation Notes

• Overflow Prevention: Since the absolute value of \(A_i\) can be up to \(10^9\), \(C\) up to \(10^9\), and \(N\) up to \(10^6\), the maximum score can reach around \(2 \times 10^{15}\). It will overflow a 32-bit integer, so make sure to use a 64-bit integer (long long in C++).

• Handling \(-\infty\): Setting the initial value of \(dp1\) directly to LLONG_MIN can cause an underflow/overflow when adding \(+C\) or \(+A_i\). It is safer to use a sufficiently small value with margin (such as LLONG_MIN / 4), or handle it via branching like “do not form a \(+C\) candidate when \(dp1\) is \(-\infty\)”. Alternatively, you can avoid \(-\infty\) entirely by initializing \(dp[1][0]=0,\ dp[1][1]=A_1\) and looping from \(i=2\) onwards.

• Memory and Fast I/O: Storing \(A\) in an array is fine since \(N \le 10^6\), but an array is actually unnecessary because the DP can be updated on the fly while reading each \(A_i\) one by one. Reading \(10^6\) integers can be slow with standard I/O; in C++, using scanf or fast I/O (e.g., bulk reading with fread and custom parsing), or in Python using sys.stdin, is recommended.

• Cases Where the Answer is 0: Since choosing not to clear any stages is allowed, the answer will be \(0\) when all values are negative and the bonus cannot overcome the loss. An implementation starting from \(dp[0][0]=0\) naturally accounts for this.

  Source Code

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

static char buf[1 << 25];

int main() {
    size_t len = fread(buf, 1, sizeof(buf) - 1, stdin);
    buf[len] = '\0';
    char *p = buf;
    auto readInt = [&]() -> long long {
        while (*p && (*p < '0' || *p > '9') && *p != '-') ++p;
        bool neg = false;
        if (*p == '-') { neg = true; ++p; }
        long long x = 0;
        while (*p >= '0' && *p <= '9') { x = x * 10 + (*p - '0'); ++p; }
        return neg ? -x : x;
    };

    long long n = readInt();
    long long C = readInt();

    const long long NEG = LLONG_MIN / 4;
    long long dp0 = 0, dp1 = NEG;
    for (long long i = 0; i < n; ++i) {
        long long a = readInt();
        long long n0 = max(dp0, dp1);
        long long cand = dp0;
        if (dp1 > NEG) cand = max(cand, dp1 + C);
        long long n1 = cand + a;
        dp0 = n0;
        dp1 = n1;
    }
    printf("%lld\n", max(dp0, dp1));
    return 0;
}

---

This editorial was generated by claude5opus-high.