Overview

This problem asks us to choose whether to “operate” or “rest” on each of the \(N\) days in order to maximize the total profit. We cannot rest for 2 or more consecutive days, and a cost of \(C\) is incurred from the 2nd consecutive day of operation onwards. This can be solved not with typical interval DP, but with DP that tracks “the state of the previous day” (a state DP similar to bitmask DP).

Analysis

Key Observation

The profit on any given day is determined solely by the choice made on that day (operate/rest) and the choice made on the previous day.

• Rest on day \(i\) \(\to\) profit of \(0\). However, this is forbidden if the previous day was also a rest day.
• Operate on day \(i\) \(\to\) profit is \(A_i\) if the previous day was a rest day (or if \(i=1\)), and \(A_i - C\) if the previous day was also an operating day.

In other words, by keeping track of just 1 bit of information—whether the previous day was an operating day or a rest day—we have all the necessary information to make decisions for day \(i\) and onwards. Detailed history from the past (such as how many consecutive days it has been operating) is unnecessary. This is the crucial point, which is guaranteed by the condition in the problem statement: “a cost of \(C\) is incurred regardless of the number of consecutive days operated.”

Issues with Naive Approaches

Trying all combinations of operating/resting results in \(2^N\) possibilities, which will not run in time at all for \(N \le 10^6\).

Furthermore, a greedy strategy such as “operate on days where \(A_i > 0\) and rest on days where \(A_i \le 0\)” is incorrect. For example, in the case of:

N=3, C=0, A = [5, -1, 5]

one might want to rest on day \(2\), but since \(C=0\), operating on day \(2\) as well yields \(5 + (-1-0) + (5-0) = 9\) as optimal (resting on day \(2\) yields \(5+0+5=10\), and there are cases where this is better); conversely, in:

N=3, C=100, A = [5, 5, 5]

operating every day gives \(5 + (5-100) + (5-100) = -185\), whereas resting on day \(2\) gives \(5 + 0 + 5 = 10\), which is optimal. As seen here, the optimal solution changes depending on the balance between \(C\) and \(A_i\), so decisions cannot be made based on local choices alone.

Solution

By using DP with two states representing “the previous day was an operating day / rest day”, transitions for each day can be computed in \(O(1)\) time, solving the problem in \(O(N)\) overall.

Algorithm

DP definitions:

• \(\mathrm{work}[i]\): The maximum total profit considering up to day \(i\), given that day \(i\) is an operating day
• \(\mathrm{rest}[i]\): The maximum total profit considering up to day \(i\), given that day \(i\) is a rest day

Initial values (\(i=1\)): $\(\mathrm{work}[1] = A_1,\qquad \mathrm{rest}[1] = 0\)$

(When operating on day \(1\), there is no previous day, so \(C\) is not subtracted.)

Transitions (\(i \ge 2\)):

• If resting on day \(i\), the previous day must have been an operating day (resting for 2 consecutive days is forbidden), so: $\(\mathrm{rest}[i] = \mathrm{work}[i-1]\)$
• If operating on day \(i\), the previous day can be either an operating day or a rest day, so: $\(\mathrm{work}[i] = \max\bigl(\mathrm{rest}[i-1] + A_i,\ \ \mathrm{work}[i-1] + A_i - C\bigr)\)$

Answer: $\(\max(\mathrm{work}[N],\ \mathrm{rest}[N])\)$

Since states outside the period are not considered, either state is acceptable on the final day.

Walkthrough with a Concrete Example

For \(N=3, C=100, A=[5,5,5]\):

\(i\)	\(\mathrm{work}\)	\(\mathrm{rest}\)
1	\(5\)	\(0\)
2	\(\max(0+5,\ 5+5-100) = 5\)	\(5\)
3	\(\max(5+5,\ 5+5-100) = 10\)	\(5\)

The answer is \(\max(10,5)=10\), showing that “operate, rest, operate” is optimal.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array; the DP only retains the previous 2 values)

Implementation Notes

• Using two variables instead of an array: Since computing \(\mathrm{work}[i]\) requires \(\mathrm{rest}[i-1]\), be careful with the update order. It is safe to store the new values in temporary variables nrest and nwork before assigning them (executing rest = work first will overwrite the old rest).

• Handling \(N=1\): The loop will not run, and the answer is \(\max(A_1, 0)\). The code above outputs \(\max(\mathrm{work},\mathrm{rest}) = \max(A_1,0)\) using just the initial values, so no special case handling is needed.

• Integer Overflow: Since \(|A_i| \le 10^9\) and \(N \le 10^6\), the total sum can reach around \(10^{15}\). Use long long in languages like C++ (this is not an issue in Python since it supports arbitrary-precision integers).

• Fast I/O: Since \(N \le 10^6\), instead of calling input() repeatedly in Python, read the entire input at once using sys.stdin.buffer.read().split(). Furthermore, converting elements with int() on the fly during the loop instead of building a full list can improve constant-factor performance.

• Note that resting “always yields a profit of 0”: \(\mathrm{rest}[i] = \mathrm{work}[i-1] + 0\), meaning \(A_i\) is not added.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    c = int(data[1])
    NEG = float('-inf')
    a1 = int(data[2])
    rest = 0
    work = a1
    for i in range(1, n):
        ai = int(data[2 + i])
        nrest = work
        nwork = rest + ai
        w2 = work + ai - c
        if w2 > nwork:
            nwork = w2
        rest = nrest
        work = nwork
    ans = rest if rest > work else work
    sys.stdout.write(str(ans) + "\n")

main()

---

This editorial was generated by claude5opus-high.