Overview

Given the number of apples \(H_i\) on each tree, only trees meeting the threshold \(H_i \ge K\) can contribute to the total. We want to maximize this total over a contiguous interval of length at most \(M\).

Analysis

First, focus only on the “shippable apples.” When choosing an interval \((L, R)\), the shipped amount is the sum of \(H_i\) for trees within the interval satisfying \(H_i \ge K\). Define:

• \(A_i = \begin{cases} H_i & (H_i \ge K) \\ 0 & (H_i < K) \end{cases}\)

Then the desired value becomes “the maximum sum of \(A_i\) over a contiguous subarray of length at most \(M\).”

The next key observation is that all \(A_i\) are non-negative (at least \(0\)). Since they are non-negative, the sum of an interval never decreases when extending it to the left or right. In other words:

• It is always at least as good to make the length exactly \(M\) (the maximum allowed) rather than choosing any shorter length (the sum stays the same or increases).

(However, if \(M \ge N\), we can simply take the entire array \(1..N\).)

Therefore: - If \(M \ge N\), the answer is the total \(\sum A_i\). - If \(M < N\), we need to find the maximum sum over intervals of exactly length \(M\).

Naively trying all intervals would result in \(O(NM)\) operations, which is far too slow for \(N \le 10^6\). Instead, we use the classic sliding window technique to find the maximum sum over fixed-length intervals in \(O(N)\).

Algorithm

1. Compute \(A_i = (H_i \ge K\ ?\ H_i : 0)\) from each \(H_i\) (in the implementation, this conversion is done in-place).
2. Case 1: \(M \ge N\)
   • Output the sum of all \(A_i\).
3. Case 2: \(M < N\)
   • Compute the sum of the first \(M\) elements as window.
   • For each \(i = M, M+1, \dots\), slide the window one position to the right:
     • Add the newly entering value, subtract the old value that falls out.
     • Update the maximum of window.
   • Output the final maximum value.

In the implementation, an array buf is used as a ring buffer to hold the most recent \(M\) elements, allowing the “old value that falls out” to be retrieved in \(O(1)\).

(Example) - \(H=[12, 5, 10, 3, 20],\ K=10 \Rightarrow A=[12,0,10,0,20]\) - For \(M=3\), the sums of length-3 intervals are: - \([12,0,10]=22\) - \([0,10,0]=10\) - \([10,0,20]=30\) - The maximum is \(30\).

Complexity

• Time complexity: \(O(N)\) (each element is processed exactly once)
• Space complexity: \(O(M)\) (buffer for the sliding window)

Implementation Notes

• Since \(N \le 10^6\), using sys.stdin.buffer.read() for fast input in Python is advantageous (the code parses integers directly from the byte string).

• The total can be as large as \(10^9 \times 10^6 = 10^{15}\), but Python’s int handles this without issues.

• When \(M \ge N\), an interval of exactly length \(M\) does not exist, so a branch is added to take the entire array, keeping the logic concise.

  Source Code

import sys

def ints_from_stdin():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = ints_from_stdin()
N = next(it)
M = next(it)
K = next(it)

if M >= N:
    ans = 0
    for _ in range(N):
        h = next(it)
        if h >= K:
            ans += h
    sys.stdout.write(str(ans))
else:
    W = M
    buf = [0] * W
    window = 0
    max_sum = 0
    p = 0

    for i in range(N):
        h = next(it)
        a = h if h >= K else 0
        if i < W:
            buf[i] = a
            window += a
            if i == W - 1:
                max_sum = window
        else:
            old = buf[p]
            buf[p] = a
            window += a - old
            p += 1
            if p == W:
                p = 0
            if window > max_sum:
                max_sum = window

    sys.stdout.write(str(max_sum))

---

This editorial was generated by gpt-5.2-high.