Overview

In this problem, we must choose whether to “operate” or “rest” for each of the \(N\) days to maximize the total profit, under the conditions that a cost \(C\) is deducted when operating consecutively, and resting for \(2\) consecutive days is prohibited. Because each day’s state depends only on the previous day’s state, this can be solved in \(O(N)\) using standard DP with states.

Analysis

Key Observations

First, let us clarify how the profit for a given day is determined:

• Rest on day \(i\) \(\to\) Profit \(0\)
• Operate on day \(i\), and rested on day \(i-1\) (or \(i=1\)) \(\to\) Profit \(A_i\)
• Operate on day \(i\), and also operated on day \(i-1\) \(\to\) Profit \(A_i - C\)

In other words, the profit on day \(i\) depends solely on “the choice on day \(i\)” and “the choice on day \(i-1\)”. The number of consecutive operating days does not matter (whether it is the 2nd or 3rd consecutive day, only \(C\) is deducted).

Furthermore, the prohibited condition “cannot rest for \(2\) or more consecutive days” can also be verified using only the choices on day \(i-1\) and day \(i\).

Therefore, it is sufficient to maintain the maximum profit up to day \(i\) for each choice on day \(i\) (operate / rest). This is because the only past information needed to decide day \(i+1\) is “whether the system operated on day \(i\).”

Issues with Naive Approaches

Exhaustively searching all combinations results in \(2^N\) possibilities, which is far too slow for \(N \le 10^6\).

Additionally, a greedy approach (e.g., “operate if \(A_i > 0\), rest otherwise”) will produce incorrect answers. For example, consider \(N = 3, C = 100, A = (10, -5, 10)\). Since \(A_2 < 0\), one might want to rest on day \(2\); operating on days \(1\) and \(3\) while resting on day \(2\) yields a profit of \(10 + 0 + 10 = 20\), which is indeed optimal. On the other hand, if \(C\) is small, say \(C = 1\) with \(A = (10, -5, 10)\), operating every day gives \(10 + (-5-1) + (10-1) = 13\), so resting on day \(2\) for \(20\) is still better. Conversely, for \(A = (10, 8, 10)\) and \(C = 100\), operating on all days because \(A_i > 0\) yields \(10 + (8-100) + (10-100) = -172\), whereas operating on day \(1\), resting on day \(2\), and operating on day \(3\) achieves the optimal profit of \(20\). As shown here, whether to operate or not is intertwined with adjacent choices, so the decision cannot be made by local greedy choices alone.

Moreover, even if \(A_i\) is negative, the “no \(2\) consecutive rest days” constraint may force us to unavoidably operate on an unprofitable day (e.g., for \(N=3\) and \(A=(-5,-5,-5)\), operating only on day \(2\) is chosen to find the best possible outcome). DP is well-suited to handle these constraints properly.

Solution

We use dynamic programming with \(2\) states indicating whether the system operated or rested on that day. With \(2N\) states and a constant number of transitions per state, this can be solved in \(O(N)\).

Algorithm

We define the following DP table:

• \(\mathrm{dp}[i][0]\): The maximum profit from day \(1\) through day \(i\), given that day \(i\) is a rest day
• \(\mathrm{dp}[i][1]\): The maximum profit from day \(1\) through day \(i\), given that day \(i\) is an operating day

Base Cases (\(i = 1\))

\[\mathrm{dp}[1][0] = 0,\quad \mathrm{dp}[1][1] = A_1\]

Since the first day has no previous day, \(C\) is not deducted even if it operates.

Transitions (\(i \ge 2\))

If we rest on day \(i\), the previous day must have been an operating day because resting for two consecutive days is prohibited:

\[\mathrm{dp}[i][0] = \mathrm{dp}[i-1][1]\]

If we operate on day \(i\), the previous day could have been either a rest day or an operating day, with \(C\) deducted if the previous day was an operating day:

\[\mathrm{dp}[i][1] = \max\bigl(\mathrm{dp}[i-1][0] + A_i,\ \ \mathrm{dp}[i-1][1] + A_i - C\bigr)\]

Answer

\[\max\bigl(\mathrm{dp}[N][0],\ \mathrm{dp}[N][1]\bigr)\]

Since states beyond day \(N\) are not considered, the final day may be either an operating day or a rest day.

Concrete Example

For \(N = 4\), \(C = 3\), \(A = (5, 4, -2, 6)\):

\(i\)	\(A_i\)	\(\mathrm{dp}[i][0]\) (Rest)	\(\mathrm{dp}[i][1]\) (Operate)
1	5	\(0\)	\(5\)
2	4	\(5\)	\(\max(0+4,\ 5+4-3) = 6\)
3	-2	\(6\)	\(\max(5-2,\ 6-2-3) = 3\)
4	6	\(3\)	\(\max(6+6,\ 3+6-3) = 12\)

The answer is \(\max(3, 12) = 12\). In fact, choosing “Operate, Operate, Rest, Operate” gives \(5 + (4-3) + 0 + 6 = 12\).

Note that because \(\mathrm{dp}[i][0]\) only permits operating on the previous day, it is always defined for \(i \ge 2\) (\(\mathrm{dp}[i-1][1]\) always holds a valid value). Therefore, unreachable states do not actually occur, but it is safe practice in implementations to support \(-\infty\) just in case.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) (if processing on the fly while reading the input; \(O(N)\) even if storing \(A\) in an array)

Implementation Notes

1. Watch out for overflow: Since \(|A_i| \le 10^9\) and \(N \le 10^6\), the absolute value of the profit can reach up to around \(10^9 \times 10^6 = 10^{15}\), and taking the cumulative deductions of \(C\) into account, around \(2 \times 10^{15}\). Because a 32-bit int (up to approx. \(2 \times 10^9\)) will overflow, use 64-bit integers (long long).

2. Arrays are not required: Since \(\mathrm{dp}[i]\) depends only on \(\mathrm{dp}[i-1]\), we can reuse two variables dp0 and dp1 to achieve \(O(1)\) space. When updating, make sure to “compute the new values in temporary variables before assigning them” (overwriting dp1 first will corrupt the transition calculation for dp0).

3. Fast I/O: Since \(N\) is up to \(10^6\), in C++ it is safe to use cin with ios::sync_with_stdio(false); cin.tie(nullptr);, or use custom parsing via fread as shown in the code above. Do not forget to handle parsing negative signs (-).

4. The \(N = 1\) case: The loop does not execute, and the answer is \(\max(0, A_1)\) (if \(A_1\) is negative, resting gives \(0\)). The implementation above handles this correctly using only the initial values.

5. Cases where \(C = 0\) or \(C\) is very large are handled naturally by the same formulas, so no special case branching is required.

   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 v = 0;
        while (*p >= '0' && *p <= '9') { v = v * 10 + (*p - '0'); ++p; }
        return neg ? -v : v;
    };

    long long N = readInt();
    long long C = readInt();

    const long long NEG = LLONG_MIN / 4;
    long long dp0, dp1; // 0: rest today, 1: work today
    long long a1 = readInt();
    dp0 = 0;
    dp1 = a1;
    for (long long i = 2; i <= N; ++i) {
        long long a = readInt();
        long long n0 = (dp1 == NEG ? NEG : dp1);
        long long cand1 = (dp0 == NEG ? NEG : dp0 + a);
        long long cand2 = (dp1 == NEG ? NEG : dp1 + a - C);
        long long n1 = max(cand1, cand2);
        dp0 = n0;
        dp1 = n1;
    }
    long long ans = max(dp0, dp1);
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.