Overview

In this problem, we need to choose whether to operate or rest on each day to maximize the total profit, under the condition that we cannot rest on consecutive days. We can solve this using dynamic programming (DP) with \(2\) states representing whether the last day was an “operating” day or a “resting” day.

Analysis

Since there are \(2\) choices (operating or resting) for each day, enumerating all possible schedules would yield \(2^N\) candidates. This will not run in time for \(N \le 10^6\).

Furthermore, a greedy approach that only considers the profit of the current day is not correct. This is because today’s choice affects whether maintenance costs will be incurred tomorrow and whether resting will be allowed tomorrow.

For example, consider the case where \(N=2,\ C=10,\ A=(1,10)\).

• If we operate on the first day, the profit on the first day is \(1\). Even if we operate the next day, the profit is \(10-10=0\), so the total profit is at most \(1\).
• If we rest on the first day and operate the next day, the total profit is \(10\).

As seen here, prioritizing immediate profit is not necessarily optimal.

Here, all that is needed to determine the next day’s profit and available choices is whether the immediately preceding day was an operating day or a resting day.

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

The number of consecutive operating days itself does not matter. Therefore, it is sufficient to record the maximum profit for each state of the last day.

Algorithm

1. DP States

We define the following two states:

• \(W_i\): the maximum total profit among valid schedules up to day \(i\), given that day \(i\) is an operating day
• \(R_i\): the maximum total profit among valid schedules up to day \(i\), given that day \(i\) is a resting day

2. Base Cases

Since the first day does not have a preceding day to consider, operating yields a profit of \(A_1\), and resting yields a profit of \(0\).

\(W_1=A_1\)

\(R_1=0\)

3. State Transitions

Consider \(i \ge 2\).

When operating on day \(i\)

Depending on the state of the previous day, there are two cases:

• Previous day was resting: Today’s profit is \(A_i\), so the total is \(R_{i-1}+A_i\).
• Previous day was operating: Today’s profit is \(A_i-C\), so the total is \(W_{i-1}+A_i-C\).

Therefore,

\(W_i=\max(R_{i-1}+A_i,\ W_{i-1}+A_i-C)\)

When resting on day \(i\)

Since we cannot rest on consecutive days, the previous day must have been an operating day. Since today’s profit is \(0\),

\(R_i=W_{i-1}\)

These transitions cover all valid choices leading to each state. Furthermore, for the same state, the choices and additional profits available from the next day onward are identical, so we only need to keep track of the maximum profit achieved up to that point. Thus, we can correctly compute the maximum profit for each day.

4. Answer and Memory Optimization

Since the final day can be either an operating day or a resting day, the answer is

\(\max(W_N,R_N)\)

Since the transitions only require the values from the previous day, there is no need to maintain an array. In the code, we can hold the previous day’s \(W_i\) and \(R_i\) in variables working and resting, respectively, and update them as we read each day’s input.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

A constant number of operations are performed for each day. Since the input can also be processed sequentially, there is no need to store the array \(A\).

Implementation Details

• Preserve values before updating
  Both next_working and next_resting are calculated from the previous day’s states. If working is overwritten first, the calculation for the resting state will be incorrect; therefore, use temporary variables before updating.

• Use 64-bit integers
  The absolute value of the total profit can reach around \(10^{15}\). Since this exceeds the range of a 32-bit integer, use long long for profits and costs in your code.

• Handle negative profits as-is
  Because we cannot rest consecutively, there may be cases where we must operate even if it incurs a loss. Do not artificially clamp the DP values to be at least \(0\).

• \(N=1\) is handled by the same logic
  Without executing the loop after initialization, \(\max(A_1,0)\) will be output. There is also no need to assume any state outside the planning period.

  Source Code

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long C;
    cin >> N >> C;

    long long A;
    cin >> A;

    long long working = A;
    long long resting = 0;

    for (int i = 1; i < N; ++i) {
        cin >> A;
        long long next_working = max(resting + A, working + A - C);
        long long next_resting = working;
        working = next_working;
        resting = next_resting;
    }

    cout << max(working, resting) << '\n';
    return 0;
}

---

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