Overview

This is a problem about harvesting as many of the \(N\) apples as possible by sinking the tree into the ground. By appropriately choosing the depth \(D\) to sink the tree, we maximize the number of apples that fall within reachable range (height \(T+K\) or less).

Analysis

1. Organizing the harvesting condition

Let \(H_i\) be the original height of the \(i\)-th apple. When the tree is sunk by \(D\) centimeters, the apple’s height becomes \(H_i - D\). Since the maximum height Takahashi can reach is \(T+K\), the condition for harvesting can be expressed by the following inequality: $\(H_i - D \leq T + K\)\( Rearranging this in terms of \)H_i\(, we get: \)\(H_i \leq T + K + D\)$

From this expression, we can see that the greater the sinking depth \(D\), the higher the apples we can reach.

2. Considering the limit on depth \(D\)

The problem statement has the constraint that “the height of the lowest apple must not become less than \(1\) centimeter.” Since \(H_i - D \geq 1\) must hold for all \(i\), rearranging in terms of \(D\): $\(D \leq H_i - 1\)\( Since this must hold for all apples, \)D\( must be at most "the height of the lowest apple \)- 1\(." Letting \)H{\min}\( be the minimum apple height, the maximum allowable \)D{\max}\( is: \)\(D_{\max} = H_{\min} - 1\)$

3. Optimal strategy

Since increasing \(D\) only increases the number of harvestable apples, it is optimal to use the maximum value \(D_{\max}\). In this case, the harvesting condition becomes: $\(H_i \leq T + K + (H_{\min} - 1)\)$

Counting the number of apples satisfying this condition gives us the answer.

Algorithm

1. Find the minimum value \(H_{\min}\) among all apple heights.
2. Calculate the maximum sinking depth \(D_{\max} = H_{\min} - 1\).
3. Calculate the reach boundary \(ReachLimit = T + K + D_{\max}\).
4. For each apple height \(H_i\), count the number of apples satisfying \(H_i \leq ReachLimit\).

Complexity

• Time complexity: \(O(N)\)
  • Finding the minimum apple height takes \(O(N)\), and counting the number satisfying the condition takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the heights of \(N\) apples in a list.

Implementation Notes

• Since \(N\) can be as large as \(2 \times 10^5\), in Python it is efficient to read input quickly using sys.stdin.read().split() or similar methods.

• Since apple heights \(H_i\) can be as large as \(10^9\), the computation process handles large numbers (up to about \(3 \times 10^9\)), but the integer types of modern programming languages (including Python) can handle this without any issues.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの個数
    # T: 高橋君の身長
    # K: 背伸びで届く追加の高さ
    N = int(input_data[0])
    T = int(input_data[1])
    K = int(input_data[2])
    
    # H: 各りんごの高さ
    H = list(map(int, input_data[3:]))
    
    # 木を沈める深さを D とすると、収穫条件は H_i - D <= T + K となる。
    # すなわち、H_i <= T + K + D を満たすりんごを収穫できる。
    # D を大きくするほど収穫できるりんごの個数は（単調に）増加するため、
    # 制約の範囲内で最大の D を選択するのが最適である。
    
    # 制約: すべての i について H_i - D >= 1
    # これより、D <= H_i - 1 がすべての i について成り立つ必要がある。
    # したがって、D の最大値 D_max は min(H_i) - 1 となる。
    H_min = min(H)
    D_max = H_min - 1
    
    # 最大の深さ D_max を用いたときの手が届く高さの境界
    reach_limit = T + K + D_max
    
    # 条件 H_i <= reach_limit を満たすりんごの個数をカウント
    ans = 0
    for h in H:
        if h <= reach_limit:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.