分数: 300 分
问题陈述
高桥正在计划旅行。
高桥有 N 智能手机。每部智能手机的编号为 1 to N和智能手机 i 目前的电池电量为 A_i %。电池电量以整数值进行管理,并且永远不会低于 0 %.
电池电量为 L % 或以下则断电且无法使用。因此,智能手机 i 与 A_i \leq L 目前已从一开始就断电。智能手机一旦关机,就永远无法再次使用。
高桥有一块手机电池。设当前时间为时间 0。时 0,高桥最多可以选择 K 智能手机(可能 0)从当前已开机的智能手机中选择并将其连接到移动电池。连接到移动电池的智能手机保持连接状态,直到所有处理完成为止 Y 已完成,在此期间他们的电池电量根本没有减少。无法中途断开连接或将连接切换到其他智能手机。此外,关闭的智能手机无法连接到移动电池。
移动电池连接完成后,每次 1,时间 2, \ldots,时间 Y,按此顺序执行以下操作:
- 电池消耗: 对于每部未连接移动电池且已开机的智能手机,其电池电量会减少 1 %.
- 断电检查: 对于未连接移动电池的智能手机,任何电池电量已变为 L % 或更少已断电。
高桥最优选择连接移动电池的智能手机时,求此时所有处理后立即开机(可用)的智能手机的最大数量 Y 已完成。连接到移动电池的智能手机如果已开机,也会被计算在内。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq L \leq 99
- 0 \leq K \leq N
- 1 \leq Y \leq 100
- 1 \leq A_i \leq 100
- 所有输入均为整数
输入
N L K Y A_1 A_2 \ldots A_N
- 第一行包含 N 代表智能手机的数量, L 代表智能手机关闭时的电池电量阈值, K 代表移动电池可同时连接的智能手机的最大数量,以及 Y 表示经过的时间,以空格分隔。
- 第二行包含 A_1, A_2, \ldots, A_N 代表每部智能手机的当前电池电量,以空格分隔。
输出
一行打印一次所有处理后立即开机的智能手机的最大数量 Y 已完成。
示例输入 1
5 10 2 5 50 12 8 30 14
示例输出 1
4
示例输入 2
8 20 3 10 100 35 25 50 18 30 22 80
示例输出 2
7
示例输入 3
10 0 1 50 100 48 51 30 75 50 60 10 49 55
示例输出 3
6