Overview

When you can uniformly lower the height of all apples by \(D\), maximize the number of apples reachable by stretching alone (\(H_i - D \le T + K\)) while satisfying the constraint \(H_i - D \ge 1\).

Analysis

After lowering the apples by \(D\) cm, the condition for the \(i\)-th apple to be reachable by stretching alone is [ H_i - D \le T+K ] Rearranging this gives [ H_i \le T+K+D ] which can be interpreted as “an apple is reachable if its original height \(H_i\) is at most the threshold \(T+K+D\).”

The key observations here are the following two points:

• Increasing \(D\) (lowering more deeply) never decreases the number of reachable apples
  Since the threshold \(T+K+D\) increases, the number of apples satisfying \(H_i \le T+K+D\) monotonically increases (stays the same or increases).

• \(D\) has an upper limit
  From the requirement “the lowest apple must not go below 1 cm,” we need \(H_i - D \ge 1\) for all \(i\). In particular, for the minimum value \(m = \min(H)\): [ m - D \ge 1 \Rightarrow D \le m-1 ] That is, the maximum possible lowering amount is \(D_{\max} = m - 1\).

From the above, since the number of reachable apples (monotonically) increases as \(D\) increases, the optimal solution is always to choose \(D = D_{\max} = m - 1\).

A naive “brute-force over all \(D\)” approach is impractical since \(D\) can be up to \(10^9\), but thanks to the monotonicity above, brute-force is unnecessary.

Concrete example: When \(H = [3, 10],\ T+K = 7\)
- \(D = 0\): Only \(3\) is reachable (1 apple)
- Maximum \(D = m - 1 = 2\): Heights become \([1, 8]\), \(1\) is reachable but \(8\) is not (still 1 apple)
Another example: \(H = [5, 6, 10],\ T+K = 7\)
- \(D = 0\): \(5, 6\) are reachable (2 apples)
- \(D = 4\) (maximum, since \(m = 5\) so \(m - 1 = 4\)): Threshold is \(7 + 4 = 11\), all original heights are \(\le 11\), so all 3 apples are reachable.

Algorithm

1. Find the minimum value \(m = \min(H)\) of the array \(H\).
2. Set the maximum lowering amount to \(D = m - 1\).
3. Count the number of elements satisfying the stretching condition \(H_i \le T + K + D\).
4. Output that count.

Complexity

• Time complexity: \(O(N)\) (one pass each for computing the minimum and counting)
• Space complexity: \(O(N)\) (storing the input array \(H\))

Implementation Notes

• The maximum lowering amount is always \(D = \min(H) - 1\) (it never becomes negative: since \(H_i \ge 1\), \(D \ge 0\) is guaranteed).

• You may directly compute the “post-lowering” values for the check, but to avoid overflow and for simplicity, it is cleaner to use the rearranged form \(H_i \le T + K + D\) for counting.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, T, K = map(int, input().split())
    H = list(map(int, input().split()))
    m = min(H)
    D = m - 1  # maximum possible lowering
    limit = T + K + D
    ans = sum(1 for h in H if h <= limit)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.