Overview

In this problem, we need to choose whether to “operate” or “halt” a factory on each of the \(N\) days to maximize the total profit earned. Since the profit obtained and the available choices (halting for two consecutive days is prohibited) depend on the state of the previous day, this problem can be solved efficiently using Dynamic Programming (DP).

Analysis

1. Naive Approach (Exhaustive Search) and Its Limitations

For each day, there are \(2\) choices: “operate” or “halt”, resulting in up to \(2^N\) possible operating schedules. With the constraint \(N \le 10^6\), an exhaustive search that explores all possible cases will far exceed the time limit (resulting in TLE).

2. Focusing on the Problem Structure

To determine the action and profit on day \(i\), the only necessary information is not the entire past history, but simply “whether the factory was operating or halted on the immediately preceding day (day \(i-1\)).” Specifically, the following rules apply: - If the factory was halted on day \(i-1\): - Day \(i\) must be operated (because halting for two consecutive days is prohibited). - The profit obtained at this time is \(A_i\). - If the factory was operating on day \(i-1\): - Day \(i\) can be halted (the profit obtained is \(0\)). - Day \(i\) can also be operated (the profit obtained is \(A_i - C\)).

Since we can determine the optimal choice for each day as long as we keep track of the “state of the previous day,” we can apply Dynamic Programming (DP).

Algorithm

For each day, we maintain \(2\) states indicating whether the factory was “halted” or “operated”.

DP Table (State) Definition

We define the maximum profit obtained after deciding up to day \(i\) (\(1 \le i \le N\)) as follows: - \(dp[i][0]\): The maximum profit when day \(i\) is halted - \(dp[i][1]\): The maximum profit when day \(i\) is operated

Initial Values (Day 1)

• When halting on day 1: the profit is \(0\), so \(dp[1][0] = 0\).
• When operating on day 1: since there is no previous day, no maintenance cost is incurred and the profit is \(A_1\), so \(dp[1][1] = A_1\).

State Transitions (\(i = 2, 3, \dots, N\))

• When halting on day \(i\) (\(dp[i][0]\)): Since we cannot halt for two consecutive days, the factory must have been operating on the previous day. $\(dp[i][0] = dp[i-1][1]\)$
• When operating on day \(i\) (\(dp[i][1]\)): We choose whichever yields a greater profit between the previous day being halted and the previous day also being operated.
  • If the previous day was halted: \(+ A_i\) to the profit up to the previous day
  • If the previous day was also operated: \(+ A_i - C\) to the profit up to the previous day $\(dp[i][1] = \max(dp[i-1][0] + A_i, \; dp[i-1][1] + A_i - C)\)$

Calculating the Answer

After computing up to day \(N\), the answer is the maximum between halting and operating on the final day. $\(\text{Answer} = \max(dp[N][0], \; dp[N][1])\)$

Note that since the transition for day \(i\) only uses values from day \(i-1\), we do not need to store the entire table for all \(N\) days; the memory usage can be optimized to \(O(1)\) by updating only \(2\) variables representing the state of the previous day.

Complexity

• Time Complexity: \(O(N)\) For each day, we only perform a constant number of additions and comparisons. Even for \(N = 10^6\), the algorithm runs very fast, taking only a few to several tens of milliseconds.
• Space Complexity: \(O(N)\) Storing the sequence \(A\) requires \(O(N)\) memory (the DP transitions themselves require only \(O(1)\) auxiliary space if we only keep the values from the previous day).

Implementation Notes

• Beware of Integer Overflow: Since \(N \le 10^6\) and \(A_i, C \le 10^9\), the total profit can reach up to approximately \(10^6 \times 10^9 = 10^{15}\). Furthermore, if losses accumulate, the value can become large in the negative direction. Because these values far exceed the range of a standard 32-bit signed integer (int, approximately \(\pm 2 \times 10^9\)), make sure to use a 64-bit integer type (such as long long in C++) for the DP table and the variable storing the answer.

• Corner Case where \(N = 1\): When \(N = 1\), the loop is not executed at all, and \(\max(0, A_1)\) is output. If \(A_1 < 0\), halting (profit \(0\)) is chosen, and if \(A_1 \ge 0\), operating (profit \(A_1\)) is chosen, which correctly satisfies the conditions of the problem.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long C;
    if (!(cin >> N >> C)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    long long dp0 = 0;      // 前日休止
    long long dp1 = A[0];   // 前日稼働

    for (int i = 1; i < N; ++i) {
        long long next_dp0 = dp1;
        long long next_dp1 = max(dp0 + A[i], dp1 + A[i] - C);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }

    cout << max(dp0, dp1) << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.