← 返回题目列表

AtCoder · awc0038_c

C. 割绳子

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

分数: 366 分

问题陈述

高桥是工艺班的老师。在今天的课程中,他计划教学生们使用绳子的手艺。

有 N 教室里的学生,高桥有一根长度相同的绳子 L。他想把这根绳子切成碎片,分发给学生们,让尽可能多的学生参与其中。

以下规则适用于切割和分配绳索:

  • 绳索的切割次数介于 0 和 K,包括在内。通过选择 k (0 \leq k \leq K) 定位在单根绳子上并切割它,绳子被精确地分成 k + 1 件。每一段的长度可以是任何正实数(即任何大于的实数) 0).
  • 每件作品最多可以送给一名学生。允许某些作品不提供给任何学生。
  • 每个学生最多可获得一件。允许某些学生不收到任何作品。
  • 的 i第学生 (1 \leq i \leq N) 可以参与工艺当且仅当他们收到至少一段长度 A_i.

当高桥最优地选择如何切断绳子以及如何将碎片分发给学生时,找到可以参与手工制作的最大学生人数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N L K
A_1 A_2 \ldots A_N
  • 第一行包含 N 代表学生人数, L 代表绳子的长度,以及 K 代表最大切割次数,以空格分隔。
  • 第二行包含 A_1, A_2, \ldots, A_N,每个学生参与工艺所需的最小绳索长度,以空格分隔。

输出

在一行中打印当绳子被切断并最佳分配时可以参与工艺的最大学生人数。


示例输入 1

4 10 2
3 2 4 5

示例输出 1

3

示例输入 2

5 15 3
5 3 4 6 2

示例输出 2

4

示例输入 3

8 1000000000 5
100000000 200000000 150000000 300000000 50000000 250000000 400000000 100000000

示例输出 3

6