Overview

For each day, we choose whether to operate or rest, aiming to maximize the total profit without resting on consecutive days. This can be solved using dynamic programming (DP) by focusing only on the state of the previous day.

Analysis

If we examine all possible combinations of operating and resting for each day, there are \(2^N\) candidates. Since \(N \le 10^6\), this approach will not run in time.

Furthermore, a greedy approach that makes decisions based only on the profit of the current day will not work. This is because the choice made today affects whether we can rest tomorrow and whether maintenance costs will be incurred.

For example, when \(C=0\) and \(A=(-1,-100)\), if we greedily choose to rest on the first day for immediate gain, we are forced to operate on the next day, resulting in a total profit of \(-100\). On the other hand, if we operate on the first day and rest on the next day, the total profit is \(-1\).

The crucial point here is that the only thing affecting the choices and profit for the next day is whether the immediately preceding day was operating or resting.

• If the previous day was operating, we can choose either to operate or rest today. However, operating incurs a cost \(C\).
• If the previous day was resting, we must operate today. The cost \(C\) is not incurred.

Since the number of consecutive operating days is irrelevant, it is sufficient to track only the following \(2\) states.

Algorithm

1. DP States

For a valid schedule up to day \(i\), we define:

• \(\mathrm{active}_i\): the maximum total profit if we operate on day \(i\)
• \(\mathrm{resting}_i\): the maximum total profit if we rest on day \(i\)

2. Initial Values

For the first day, states prior to the planning period are not considered. Therefore:

• If operating, the profit is \(A_1\)
• If resting, the profit is \(0\)

The initial values are as follows:

\(\mathrm{active}_1=A_1\)

\(\mathrm{resting}_1=0\)

3. State Transitions

Let \(i \ge 2\).

When operating on day \(i\)

Depending on the state of the previous day, there are \(2\) possibilities:

• Operated on the previous day as well: \(\mathrm{active}_{i-1}+A_i-C\)
• Rested on the previous day: \(\mathrm{resting}_{i-1}+A_i\)

Taking the maximum of the two:

\(\mathrm{active}_i=A_i+\max(\mathrm{active}_{i-1}-C,\ \mathrm{resting}_{i-1})\)

When resting on day \(i\)

Since consecutive rest days are not allowed, the previous day must have been an operating day. The profit for today is \(0\), so:

\(\mathrm{resting}_i=\mathrm{active}_{i-1}\)

These transitions cover all valid states from the previous day. Since future choices from the same state are identical, retaining only the maximum profit to reach that state ensures that the optimal schedule is never missed.

4. Answer

Since either operating or resting is valid on the final day, the answer is:

\(\max(\mathrm{active}_N,\ \mathrm{resting}_N)\)

Because each day’s calculation only depends on the values of the previous day, an array is not required. In the code, we sequentially update just the \(2\) variables active and resting.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) auxiliary space for the DP. However, since the provided code reads the input all at once with read().split(), it is \(O(N)\) including the space required to store the input.

Implementation Notes

• You must use the values prior to updating.
  In the code, we first compute new_active, and then update them in the order resting = active followed by active = new_active. Overwriting active first would incorrectly use the current day’s value when computing the resting state.

• Retain states even if intermediate profits are negative.
  Because consecutive rest days are not allowed, there are situations where operating at a loss is required. DP values should not be arbitrarily clamped to \(0\) or higher.

• \(N=1\) can be handled by the exact same logic.
  The update loop will simply not execute, and \(\max(A_1,0)\) will be output.

• Total profit may exceed the range of a 32-bit integer.
  This is not an issue with Python’s arbitrary-precision integers, but in other languages, a 64-bit integer type must be used.

  Source Code

import sys


def main():
    values = map(int, sys.stdin.buffer.read().split())
    n = next(values)
    c = next(values)

    active = next(values)
    resting = 0

    for a in values:
        continued = active - c
        new_active = a + (continued if continued > resting else resting)
        resting = active
        active = new_active

    print(active if active > resting else resting)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.