Overview

Given \(N\) trees, we need to select a contiguous interval of at most \(M\) trees and maximize the total number of apples from trees within that interval satisfying \(H_i \geq K\). This can be solved efficiently using prefix sums and the sliding window technique.

Analysis

Problem Reformulation

When we select an interval \([L, R]\), the total number of apples that can be shipped is:

\[\sum_{i=L}^{R} A_i \quad \text{where} \quad A_i = \begin{cases} H_i & (H_i \geq K) \\ 0 & (H_i < K) \end{cases}\]

In other words, if we first construct a new array \(A\) where each element is “\(H_i\) if the tree meets the shipping criteria, \(0\) otherwise,” the problem reduces to finding the maximum sum of a contiguous subarray of length at most \(M\).

Key Observation: \(A_i \geq 0\)

For a general array, finding the “maximum sum of a subarray of length at most \(M\)” requires maintaining the minimum of the prefix sum using a sliding window minimum (e.g., with a deque).

However, since \(A_i \geq 0\) in this problem, the prefix sum \(\text{prefix}[i]\) is monotonically non-decreasing. This means:

• The sum of interval \([L, R]\) (1-indexed) is \(\text{prefix}[R] - \text{prefix}[L-1]\)
• To maximize this with a fixed \(R\), we need to minimize \(\text{prefix}[L-1]\)
• The range of \(L-1\) is \([\max(0, R-M),\, R-1]\), and since prefix is monotonically non-decreasing, the minimum is always achieved at the left endpoint \(\max(0, R-M)\)

This means it is always optimal to use the maximum allowed length \(M\) for the interval (making it shorter never helps).

Concrete Example

For \(N=5, M=3, K=3, H=[1, 5, 2, 4, 1]\):

• \(A = [0, 5, 0, 4, 0]\) (trees with height less than \(K=3\) become \(0\))
• \(\text{prefix} = [0, 0, 5, 5, 9, 9]\)
• Compute the window sum of width \(M=3\) for each right endpoint \(R\):
  • \(R=1\): \(\text{prefix}[1] - \text{prefix}[0] = 0\)
  • \(R=2\): \(\text{prefix}[2] - \text{prefix}[0] = 5\)
  • \(R=3\): \(\text{prefix}[3] - \text{prefix}[0] = 5\)
  • \(R=4\): \(\text{prefix}[4] - \text{prefix}[1] = 9\)
  • \(R=5\): \(\text{prefix}[5] - \text{prefix}[2] = 4\)
• The maximum is \(9\) (interval \([2, 4]\))

Algorithm

1. Construct array \(A\): \(A_i = H_i\) (when \(H_i \geq K\)), \(A_i = 0\) (otherwise)
2. Compute prefix sums \(\text{prefix}\): \(\text{prefix}[0] = 0,\; \text{prefix}[i] = \text{prefix}[i-1] + A_{i-1}\)
3. For each \(R = 1, 2, \ldots, N\), compute \(\text{prefix}[R] - \text{prefix}[\max(0, R-M)]\) and take the maximum

Complexity

• Time complexity: \(O(N)\) — array construction, prefix sum computation, and maximum search are each \(O(N)\)
• Space complexity: \(O(N)\) — for storing array \(A\) and the prefix sums

Implementation Notes

• Since \(A_i \geq 0\), the prefix sum is monotonically non-decreasing, so there is no need for sliding window minimum management using a deque; a simple loop suffices

• Since \(N\) can be as large as \(10^6\), fast input using sys.stdin.buffer.read() is important in Python

• When computing the left endpoint of the window as max(0, R - M), be careful about the correspondence between 1-indexed and 0-indexed representations

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    H = [int(input_data[3 + i]) for i in range(N)]
    
    # For each tree, if H[i] >= K, its contribution is H[i], else 0
    # We need to find a window of size <= M that maximizes the sum of H[i] where H[i] >= K
    
    # Create array of filtered values
    A = [h if h >= K else 0 for h in H]
    
    # Compute prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # For each R (1-indexed end), the window starts at L where L >= R - M + 1 and L >= 1
    # Sum = prefix[R] - prefix[L-1]
    # To maximize, we want prefix[L-1] to be minimized over L in [max(1, R-M+1), R]
    # i.e., prefix[j] minimized over j in [max(0, R-M), R-1]
    
    # Since A[i] >= 0, prefix is non-decreasing, so the minimum prefix[j] is at j = max(0, R-M)
    # Therefore the best window ending at position R (1-indexed) has sum = prefix[R] - prefix[max(0, R-M)]
    
    ans = 0
    for r in range(1, N + 1):
        l_start = max(0, r - M)
        s = prefix[r] - prefix[l_start]
        if s > ans:
            ans = s
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.