← 返回题目列表

AtCoder · awc0009_c

C. 苹果丰收

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在果园做一份摘苹果的兼职工作。果园有 N 苹果,每个位于树上的不同高度。

的 i-第一个苹果的高度为 H_i 距地面厘米。高桥的身高是 T 厘米,但通过伸展脚趾,他可以达到的最大高度 T + K 厘米。

要收获苹果,苹果的高度必须在他够得着的范围内(最多 T + K 厘米)。对于他够不到的苹果,他需要使用活梯。

由于高桥发现使用活梯很麻烦,因此他希望通过单独伸展来最大限度地增加收获的苹果数量。幸运的是,这个果园里的树都是种植在特制的移动花盆里的,他可以挖一个深度的洞 D 厘米在地下沉入整个花盆(D 是任何非负整数)。当一棵树下沉时,它所有苹果的高度都会均匀减少 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
  • 第一行包含苹果的数量 N, 高桥的身高 T,以及附加高度 K 他可以通过伸展来到达,之间有空格。
  • 第二行包含每个苹果的高度 H_1, H_2, \ldots, H_N,用空格分隔。

输出

在一行中打印 Takahashi 通过单独拉伸可以收获的最大苹果数量。


示例输入 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