C - Apple Harvest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は果樹園でりんごの収穫アルバイトをしています。果樹園には N 個のりんごがなっており、それぞれのりんごは木の異なる高さの位置にあります。

i 番目のりんごは地面から H_i センチメートルの高さにあります。高橋君の身長は T センチメートルですが、背伸びをすることで、最大 T + K センチメートルの高さまで手が届きます。

りんごを収穫するためには、りんごの高さが手の届く範囲内（ T + K センチメートル以下）でなければなりません。手が届かないりんごには、脚立を使う必要があります。

高橋君は脚立を使うのが面倒なので、背伸びだけで収穫できるりんごの個数を最大化したいと考えています。幸い、この果樹園の木は特殊な移動式プランターに植えられており、プランターごと地面に D センチメートルの深さの穴を掘って沈めることができます（ D は 0 以上の任意の整数）。木を沈めると、すべてのりんごの高さが一律に D だけ低くなります。

ただし、最も低い位置にあるりんごの高さが 1 センチメートル未満になってはいけないという制約があります。つまり、すべての i について H_i - D \geq 1 を満たす必要があります。

高橋君が背伸びだけで収穫できるりんごの最大個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq K \leq 10^9
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N T K
H_1 H_2 \ldots H_N
  • 1 行目には、りんごの個数 N 、高橋君の身長 T 、背伸びで追加で届く高さ K が、スペース区切りで与えられる。
  • 2 行目には、各りんごの高さ H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

高橋君が背伸びだけで収穫できるりんごの最大個数を 1 行で出力せよ。

入力例 1

5 150 30
100 160 180 200 250

出力例 1

5

入力例 2

5 100 10
50 80 120 200 300

出力例 2

3

入力例 3

10 200 50
10 30 50 100 150 200 260 300 350 400

出力例 3

6

入力例 4

15 500 100
1 50 100 200 300 400 500 550 580 590 600 650 700 800 1000

出力例 4

11

入力例 5

1 1 0
1

出力例 5

1

Score : 333 pts

Problem Statement

Takahashi is working a part-time job harvesting apples at an orchard. The orchard has N apples, each located at a different height on the tree.

The i-th apple is at a height of H_i centimeters from the ground. Takahashi's height is T centimeters, but by stretching on his toes, he can reach up to a maximum height of T + K centimeters.

To harvest an apple, the apple's height must be within his reach (at most T + K centimeters). For apples he cannot reach, he would need to use a stepladder.

Since Takahashi finds using a stepladder troublesome, he wants to maximize the number of apples he can harvest by stretching alone. Fortunately, the trees in this orchard are planted in special mobile planters, and he can dig a hole of depth D centimeters in the ground to sink an entire planter (D is any non-negative integer). When a tree is sunk, the heights of all its apples are uniformly reduced by D.

However, there is a constraint that the height of the lowest apple must not become less than 1 centimeter. In other words, for all i, the condition H_i - D \geq 1 must be satisfied.

Find the maximum number of apples Takahashi can harvest by stretching alone.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 0 \leq K \leq 10^9
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N T K
H_1 H_2 \ldots H_N
  • The first line contains the number of apples N, Takahashi's height T, and the additional height K he can reach by stretching, separated by spaces.
  • The second line contains the heights of each apple H_1, H_2, \ldots, H_N, separated by spaces.

Output

Print the maximum number of apples Takahashi can harvest by stretching alone, in a single line.

Sample Input 1

5 150 30
100 160 180 200 250

Sample Output 1

5

Sample Input 2

5 100 10
50 80 120 200 300

Sample Output 2

3

Sample Input 3

10 200 50
10 30 50 100 150 200 260 300 350 400

Sample Output 3

6

Sample Input 4

15 500 100
1 50 100 200 300 400 500 550 580 590 600 650 700 800 1000

Sample Output 4

11

Sample Input 5

1 1 0
1

Sample Output 5

1