Overview

In this problem, for each day, we must choose whether to “operate” or “halt” the factory to maximize the total profit, subject to a maintenance cost \(C\) for consecutive operational days and the constraint that the factory cannot be halted for two consecutive days.

Analysis

1. Focusing on State Dependencies

The profit earned and the valid choices on each day \(i\) depend only on whether the factory was operating or halted on the previous day (day \(i - 1\)). - If halting on day \(i\): - Since the factory cannot be halted for \(2\) consecutive days, it must have been operating on the previous day. - The profit earned is \(0\). - If operating on day \(i\): - The factory could have been either halted or operating on the previous day. - If it was halted on the previous day, the profit is \(+A_i\). - If it was also operating on the previous day, a maintenance cost is incurred, so the profit is \(+ (A_i - C)\).

2. Naive Approach and its Limitations

A brute-force search that tries both “operating” and “halted” for each day would result in \(2^N\) total combinations. Since \(N \le 10^6\) in this problem, this approach cannot finish within the time limit.

3. Solution via Dynamic Programming (DP)

The only information needed to make decisions for future days is “whether the factory was operating on the previous day” and “the maximum profit achieved up to that point.” Therefore, Dynamic Programming (DP), which records aggregated states day by day, is effective.

Algorithm

We define the following \(2\) states for the DP:

• \(dp_0\): The maximum profit so far when the factory was “halted” on the previous day.
• \(dp_1\): The maximum profit so far when the factory was “operating” on the previous day.

Initial State (Day 1)

• If halting on day \(1\): The profit is \(0\), so \(dp_0 = 0\).
• If operating on day \(1\): The profit is \(A_1\), so \(dp_1 = A_1\).

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

Update the states for day \(i\) using the values from the previous day:

1. If halting on day \(i\) (\(new\_dp_0\)): Since the factory must have been operating on the previous day, the value of \(dp_1\) from the previous day is carried over directly: $\(new\_dp_0 = dp_1\)$

2. If operating on day \(i\) (\(new\_dp_1\)):

   • If it was halted on the previous day: The total profit obtained is \(dp_0 + A_i\).
   • If it was also operating on the previous day: The total profit obtained is \(dp_1 - C + A_i\).

We take the maximum of these two options: $\(new\_dp_1 = A_i + \max(dp_0, dp_1 - C)\)$

Final Answer

After updating up to day \(N\), the state on the last day can be either halted or operating, so the answer is \(\max(dp_0, dp_1)\).

Complexity

• Time Complexity: \(O(N)\) We compute the values sequentially from day \(1\) to day \(N\), once each. Since each day’s transition takes constant time \(O(1)\), the total time complexity is \(O(N)\), which easily runs well within the time limit even for \(N = 10^6\).
• Space Complexity: \(O(N)\) Storing the input array \(A\) takes \(O(N)\) memory. The DP table itself only needs to keep the values from the previous day, so it operates using \(O(1)\) auxiliary space.

Implementation Notes

• Fast I/O: In Python, reading input can be slow when \(N\) is on the order of \(10^6\). By reading all data at once using sys.stdin.read().split(), the execution time can be significantly reduced.

• Variable Reuse: Instead of allocating a DP array of size \(N\), we can update two variables (dp0, dp1) representing the results of the previous day. This avoids unnecessary memory consumption and improves cache efficiency.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = int(input_data[1])
    
    A = [int(x) for x in input_data[2:]]
    
    dp0 = 0
    dp1 = A[0]
    
    for a in A[1:]:
        new_dp0 = dp1
        val = dp1 - C
        new_dp1 = a + (dp0 if dp0 > val else val)
        dp0 = new_dp0
        dp1 = new_dp1
        
    print(dp0 if dp0 > dp1 else dp1)

if __name__ == '__main__':
    main()

---

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