Overview

This is a problem of maximizing the total number of apples that can be shipped (meeting the shipping standard \(K\) or above) from an interval of at most \(M\) consecutive trees.

Analysis

In this problem, by choosing a consecutive interval \([L, R]\) (\(R - L + 1 \leq M\)), we can obtain apples only from trees within that interval that satisfy \(H_i \geq K\). The number of apples obtained is the sum of \(H_i\) for those trees.

Naive Approach and Its Issues

The first idea that comes to mind is to compute the sum of apples from qualifying trees for every interval \([L, R]\) (\(R - L + 1 \leq M\)). However, this requires \(O(N \cdot M)\) computation, and since \(N\) and \(M\) can be up to \(10^6\), this would require around \(10^{12}\) operations in total, which will not finish in time (TLE).

Improvement: Using Prefix Sums

If we can quickly compute the “total shippable apples” for each interval, then a full search will be fast enough. To achieve this, we create an array containing only the apple counts from shippable trees and precompute its prefix sums, allowing us to compute the sum of any interval in \(O(1)\).

Specifically: - For each \(H_i\), create an array values where the value is \(H_i\) if \(H_i \geq K\), and \(0\) otherwise. - Precompute the prefix sum array acc of this array. - With this, the sum of interval \([L, R]\) can be computed as acc[R+1] - acc[L].

By doing this, the sum for each interval can be computed in \(O(1)\), and the overall time complexity becomes \(O(N)\).

Algorithm

1. Read \(N\), \(M\), \(K\), and \(H_i\) from input.
2. For each \(H_i\), create an array values where the value is \(H_i\) if \(H_i \geq K\), and \(0\) otherwise.
3. Compute the prefix sum array acc of values (prepend \(0\) to simplify index operations).
4. For each left endpoint \(L\) (0-indexed), set the right endpoint \(R = \min(L + M, N)\) so that the interval length is at most \(M\), and compute the interval sum as acc[R] - acc[L].
5. Record and output the maximum interval sum.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• When computing the prefix sum, prepending \(0\) at the beginning makes it convenient to naturally compute the sum of interval \([L, R)\) as acc[R] - acc[L].

• Be careful with the handling of interval endpoints. In Python’s slicing and index specification, min() is used to cap the upper bound and prevent out-of-bounds access.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    H = list(map(int, data[3:3+N]))
    
    # 各木について、出荷可能ならその個数、不可なら0
    values = [h if h >= K else 0 for h in H]
    
    # 累積和を計算
    acc = [0] + list(accumulate(values))
    
    max_apples = 0
    
    # 区間[L, R] (1-indexed) に対応する 0-indexed の範囲は [L-1, R]
    # 区間長が最大Mなので、R - L + 1 <= M → R <= L + M - 1
    for L in range(N):
        R_end = min(L + M, N)
        # 区間 [L, R_end) の和 = acc[R_end] - acc[L]
        current_sum = acc[R_end] - acc[L]
        if current_sum > max_apples:
            max_apples = current_sum
            
    print(max_apples)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.