C - Cutting a Rope Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は工作教室の先生をしています。今日の授業では、生徒たちにロープを使った工作を教える予定です。

教室には N 人の生徒がおり、高橋君は長さ L のロープを1本持っています。高橋君はこのロープを切り分けて生徒たちに配ることで、できるだけ多くの生徒に工作に参加してもらいたいと考えています。

ロープの切り分けと配布には以下のルールがあります。

  • ロープを切る回数は 0 回以上 K 回以下である。1本のロープ上の好きな位置を選んで k 回 (0 \leq k \leq K) 切ると、ちょうど k + 1 本のピースに分かれる。各ピースの長さは任意の正の実数（すなわち 0 より大きい任意の実数）でよい。
  • 切り分けた各ピースは、高々1人の生徒に配ることができる。どの生徒にも配らないピースがあってもよい。
  • 各生徒が受け取れるピースは高々1本である。ピースを受け取らない生徒がいてもよい。
  • i 番目の生徒 (1 \leq i \leq N) は、長さが A_i 以上のピースを1本受け取ったとき、またそのときに限り、工作に参加できる。

高橋君がロープの切り方および生徒への配り方を最適に選ぶとき、工作に参加できる生徒の最大人数を求めてください。

制約

  • 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
  • 1 行目には、生徒の人数を表す N 、ロープの長さを表す L 、最大カット回数を表す K が、スペース区切りで与えられる。
  • 2 行目には、各生徒が工作に参加するために必要なロープの最小の長さ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

最適にロープを切り分けて配るとき、工作に参加できる生徒の最大人数を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is a teacher at a crafting class. In today's lesson, he plans to teach the students a craft using rope.

There are N students in the classroom, and Takahashi has one rope of length L. He wants to cut this rope into pieces and distribute them to the students so that as many students as possible can participate in the craft.

The following rules apply to cutting and distributing the rope:

  • The number of cuts made to the rope is between 0 and K, inclusive. By choosing k (0 \leq k \leq K) positions on a single rope and cutting it, the rope is divided into exactly k + 1 pieces. The length of each piece may be any positive real number (that is, any real number greater than 0).
  • Each piece can be given to at most one student. It is allowed for some pieces not to be given to any student.
  • Each student can receive at most one piece. It is allowed for some students not to receive any piece.
  • The i-th student (1 \leq i \leq N) can participate in the craft if and only if they receive a piece of length at least A_i.

When Takahashi optimally chooses how to cut the rope and how to distribute the pieces to the students, find the maximum number of students who can participate in the craft.

Constraints

  • 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)
  • All input values are integers.

Input

N L K
A_1 A_2 \ldots A_N
  • The first line contains N representing the number of students, L representing the length of the rope, and K representing the maximum number of cuts, separated by spaces.
  • The second line contains A_1, A_2, \ldots, A_N, the minimum rope lengths required for each student to participate in the craft, separated by spaces.

Output

Print in one line the maximum number of students who can participate in the craft when the rope is cut and distributed optimally.

Sample Input 1

4 10 2
3 2 4 5

Sample Output 1

3

Sample Input 2

5 15 3
5 3 4 6 2

Sample Output 2

4

Sample Input 3

8 1000000000 5
100000000 200000000 150000000 300000000 50000000 250000000 400000000 100000000

Sample Output 3

6