/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は、筋力トレーニングのために N 種類のエクササイズを準備しています。それぞれのエクササイズには 1 から N までの番号が付けられており、エクササイズ i のスタミナの初期値は A_i です。
各エクササイズには 残りスタミナ が設定されており、トレーニング開始前の時点では、エクササイズ i の残りスタミナは初期値 A_i に等しいです。
高橋君は毎日ちょうど1回、以下の手順でトレーニングを行います。
- N 種類のエクササイズのうち、残りスタミナが K 以上であるものの中から 1つ を選ぶ。残りスタミナが K 以上であれば、過去に何度選んだエクササイズであっても再び選ぶことができる。
- 選んだエクササイズの残りスタミナをちょうど K だけ減らす。選ばれなかったエクササイズの残りスタミナは変化しない。
手順 1 において、残りスタミナが K 以上のエクササイズが1つも存在しない場合、その日のトレーニングは行えず、それ以降もトレーニングを続けることはできません。
高橋君は M 日間のトレーニングを計画しています。すなわち、上の手順を合計 M 回行う必要があります。
高橋君がエクササイズの選び方をうまく決めることで、M 日間すべてトレーニングを行うことができるかどうかを判定してください。できる場合は Yes を、できない場合は No を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N M K A_1 A_2 \ldots A_N
- 1 行目には、エクササイズの種類数を表す整数 N、トレーニングしたい日数を表す整数 M、1回のトレーニングで消費する残りスタミナの量を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各エクササイズのスタミナの初期値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君が M 日間、毎日トレーニングを続けることができる場合は Yes を、できない場合は No を1行で出力してください。
入力例 1
3 5 2 4 3 5
出力例 1
Yes
入力例 2
3 6 2 4 3 5
出力例 2
No
入力例 3
5 5 1000000000 1000000000 1000000000 1000000000 999999999 1000000000
出力例 3
No
Score : 233 pts
Problem Statement
Takahashi is preparing N types of exercises for strength training. Each exercise is numbered from 1 to N, and exercise i has an initial stamina value of A_i.
Each exercise has a remaining stamina value. Before training begins, the remaining stamina of exercise i is equal to its initial value A_i.
Every day, Takahashi performs training exactly once according to the following procedure:
- From the N types of exercises, choose one whose remaining stamina is at least K. As long as the remaining stamina is at least K, an exercise can be chosen again regardless of how many times it has been chosen in the past.
- Decrease the remaining stamina of the chosen exercise by exactly K. The remaining stamina of exercises that were not chosen does not change.
In step 1, if there is no exercise with remaining stamina of at least K, training cannot be performed that day, and no further training can be done from that point onward.
Takahashi is planning M days of training. That is, he needs to perform the above procedure a total of M times.
Determine whether Takahashi can complete training on all M days by choosing exercises wisely. If it is possible, output Yes; otherwise, output No.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N M K A_1 A_2 \ldots A_N
- The first line contains three space-separated integers: N, the number of types of exercises; M, the number of days Takahashi wants to train; and K, the amount of remaining stamina consumed per training session.
- The second line contains space-separated integers A_1, A_2, \ldots, A_N, representing the initial stamina values of each exercise.
Output
If Takahashi can continue training every day for M days, output Yes; otherwise, output No, on a single line.
Sample Input 1
3 5 2 4 3 5
Sample Output 1
Yes
Sample Input 2
3 6 2 4 3 5
Sample Output 2
No
Sample Input 3
5 5 1000000000 1000000000 1000000000 1000000000 999999999 1000000000
Sample Output 3
No