/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は N 日間の帰省で実家に滞在しています。
実家では毎日おやつが用意されており、i 日目のおやつのカロリーは A_i です。
高橋君は体調管理のために、直近 M 日間で食べたおやつのカロリーの合計が K を超えないならばおやつを食べることを繰り返します。
具体的には i=1,2,\dots,N の順に、以下のルールに従って i 日目のおやつを食べるかどうかを決定します。
- i 日目のおやつを食べたと仮定したときに \max(i-M+1,1) 日目から i 日目までの間に食べたおやつのカロリーの合計が K 以下ならば、i 日目のおやつを実際に食べる。そうでないならば、i 日目のおやつを食べない。
i=1,2,\dots,N それぞれについて、高橋君が i 日目のおやつを食べるかどうかを判定してください。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \dots A_N
出力
N 行出力せよ。i 行目には高橋君が i 日目のおやつを食べる場合 Yes と、食べない場合 No と出力せよ。
入力例 1
5 3 83 48 73 59 90 21
出力例 1
Yes No No No Yes
それぞれの日において、おやつを食べたと仮定したときの直近 3 日間で食べたおやつのカロリーの合計は以下のようになります。
- 1 日目：48
- 2 日目：48+73=121
- 3 日目：48+59=107
- 4 日目：90
- 5 日目：21
入力例 2
7 4 728 187 816 349 609 255 308 175
出力例 2
Yes No Yes No Yes No Yes
入力例 3
10 3 1368290936 216519459 804733999 297250023 775422599 287963235 999315644 354987425 974810607 653940822 117157941
出力例 3
Yes Yes Yes No Yes Yes No No Yes Yes
Score : 300 points
Problem Statement
Takahashi is staying at his parents' house for an N-day homecoming trip.
At his parents' house, a snack is prepared every day, and the calorie count of the snack on day i is A_i.
To manage his health, he repeats the following: he eats the snack on a given day if and only if the total calorie count of the snacks he has eaten in the most recent M days does not exceed K.
Specifically, in the order i=1,2,\dots,N, he decides whether to eat the snack on day i according to the following rule:
- Assuming that he eats the snack on day i, if the total calorie count of the snacks eaten from day \max(i-M+1,1) through day i is at most K, then he actually eats the snack on day i. Otherwise, he does not eat the snack on day i.
For each i=1,2,\dots,N, determine whether Takahashi eats the snack on day i.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K A_1 A_2 \dots A_N
Output
Output N lines. The i-th line should contain Yes if Takahashi eats the snack on day i, and No otherwise.
Sample Input 1
5 3 83 48 73 59 90 21
Sample Output 1
Yes No No No Yes
For each day, assuming that he eats the snack, the total calorie count of the snacks eaten in the most recent three days is as follows:
- Day 1: 48
- Day 2: 48+73=121
- Day 3: 48+59=107
- Day 4: 90
- Day 5: 21
Sample Input 2
7 4 728 187 816 349 609 255 308 175
Sample Output 2
Yes No Yes No Yes No Yes
Sample Input 3
10 3 1368290936 216519459 804733999 297250023 775422599 287963235 999315644 354987425 974810607 653940822 117157941
Sample Output 3
Yes Yes Yes No Yes Yes No No Yes Yes