/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君はこれから N 回の小テストを受けます。i 回目の小テストにおける高橋君の点数は H_i 点です。点数は負の値になることもあります。
高橋君は 0 回以上 K 回以下の好きな回数だけ「補習授業」を受けることができます。補習授業を 1 回受けるごとに、N 回のテストの中から 1 つを選び、そのテストの点数に P を加算します。同じテストを複数回選ぶこともでき、どのテストを選んでも構いません。
すべての補習授業の割り当てが終わった後、各テストの最終的な点数を確認します。最終的な点数が 0 以下であるテストは「赤点」となります。0 点ちょうどのテストも赤点であることに注意してください。
高橋君は赤点となるテストの数をできるだけ少なくしたいと考えています。補習授業を最適に割り当てたとき、赤点となるテストの数の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq P \leq 10^9
- -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N K P H_1 H_2 \ldots H_N
- 1 行目には、小テストの回数を表す整数 N、補習授業を受けられる最大回数を表す整数 K、補習授業 1 回あたりの加算点を表す正の整数 P が、スペース区切りで与えられる。
- 2 行目には、各テストの点数を表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
出力
補習授業を最適に割り当てたとき、赤点となるテストの数の最小値を 1 行で出力せよ。
入力例 1
5 3 2 -3 1 -1 0 5
出力例 1
1
入力例 2
4 2 3 -5 -2 3 -8
出力例 2
2
入力例 3
8 10 5 -9 -4 2 -1 0 -14 7 -6
出力例 3
0
入力例 4
10 5 4 -7 -3 1 -15 0 -1 8 -10 -4 2
出力例 4
3
入力例 5
1 0 1 0
出力例 5
1
Score : 366 pts
Problem Statement
Takahashi will take N quizzes. His score on the i-th quiz is H_i points. Scores can be negative.
Takahashi can attend "supplementary lessons" any number of times from 0 to K times, inclusive. Each time he attends a supplementary lesson, he chooses one of the N quizzes and adds P to that quiz's score. He may choose the same quiz multiple times, and he may choose any quiz.
After all supplementary lessons have been assigned, the final score of each quiz is checked. A quiz whose final score is 0 or less is considered a "failing grade." Note that a quiz with a score of exactly 0 is also a failing grade.
Takahashi wants to minimize the number of quizzes with failing grades. Find the minimum number of quizzes with failing grades when the supplementary lessons are assigned optimally.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq P \leq 10^9
- -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers.
Input
N K P H_1 H_2 \ldots H_N
- The first line contains an integer N representing the number of quizzes, an integer K representing the maximum number of supplementary lessons, and a positive integer P representing the points added per supplementary lesson, separated by spaces.
- The second line contains integers H_1, H_2, \ldots, H_N representing the scores of each quiz, separated by spaces.
Output
Print in one line the minimum number of quizzes with failing grades when the supplementary lessons are assigned optimally.
Sample Input 1
5 3 2 -3 1 -1 0 5
Sample Output 1
1
Sample Input 2
4 2 3 -5 -2 3 -8
Sample Output 2
2
Sample Input 3
8 10 5 -9 -4 2 -1 0 -14 7 -6
Sample Output 3
0
Sample Input 4
10 5 4 -7 -3 1 -15 0 -1 8 -10 -4 2
Sample Output 4
3
Sample Input 5
1 0 1 0
Sample Output 5
1