/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は運送会社の配車担当です。倉庫には N 個の荷物が番号 1 から N の順に一列に並んでおり、i 番目の荷物の重さは A_i です。
これらの荷物をちょうど M 台のトラックに積み分けて配送します。積み分けは、荷物の番号の順序を保ったまま、連続する番号の荷物からなるちょうど M 個のグループに分割して行います。具体的には、0 = L_0 < L_1 < L_2 < \cdots < L_M = N を満たす整数列 L_0, L_1, \ldots, L_M を選び、k 番目 (1 \leq k \leq M) のトラックには荷物 L_{k-1}+1, L_{k-1}+2, \ldots, L_k を積みます。L_0 < L_1 < \cdots < L_M は狭義不等号であるため、各トラックには少なくとも 1 個の荷物が含まれることに注意してください。
各トラックについて、積まれた荷物の重さの合計を「積載量」と呼びます。M 台のトラックのうち積載量が最も大きいトラックに負担が集中してしまうため、高橋君は積載量の最大値ができるだけ小さくなるように荷物を分けたいと考えています。
すべての分け方の中で、積載量の最大値の最小値を S とします。整数 K が与えられるので、S > K であるかどうかを判定してください。
- どのように分けても積載量の最大値が K を超えてしまう（すなわち S > K）ならば
Yesを出力してください。 - 積載量の最大値を K 以下にできる分け方が存在する（すなわち S \leq K）ならば
Noを出力してください。
制約
- 1 \leq M \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- 1 \leq K \leq 10^{15}
- 入力はすべて整数である
入力
N M K A_1 A_2 \ldots A_N
- 1 行目には、荷物の個数を表す整数 N、トラックの台数を表す整数 M、判定の基準値を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各荷物の重さを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
S > K ならば Yes を、S \leq K ならば No を 1 行で出力せよ。
入力例 1
5 2 10 3 5 2 4 6
出力例 1
No
入力例 2
5 2 9 3 5 2 4 6
出力例 2
Yes
入力例 3
10 3 20 4 8 2 5 7 3 6 1 9 5
出力例 3
No
入力例 4
20 4 50 7 12 3 8 15 6 9 11 4 10 13 2 14 5 8 16 3 7 11 6
出力例 4
No
入力例 5
3 3 5 5 6 5
出力例 5
Yes
Score : 366 pts
Problem Statement
Takahashi is a dispatch manager at a shipping company. In the warehouse, N packages are lined up in a row, numbered from 1 to N, and the weight of the i-th package is A_i.
These packages are to be divided among exactly M trucks for delivery. The division is performed by partitioning the packages into exactly M groups of consecutively numbered packages, preserving the order of package numbers. Specifically, we choose an integer sequence L_0, L_1, \ldots, L_M satisfying 0 = L_0 < L_1 < L_2 < \cdots < L_M = N, and the k-th truck (1 \leq k \leq M) is loaded with packages L_{k-1}+1, L_{k-1}+2, \ldots, L_k. Note that since L_0 < L_1 < \cdots < L_M uses strict inequalities, each truck contains at least one package.
For each truck, the total weight of its loaded packages is called its "load". Since the truck with the largest load among the M trucks bears a disproportionate burden, Takahashi wants to divide the packages so that the maximum load is as small as possible.
Let S be the minimum possible value of the maximum load over all possible ways to divide the packages. Given an integer K, determine whether S > K.
- If the maximum load exceeds K no matter how the packages are divided (i.e., S > K), output
Yes. - If there exists a way to divide the packages such that the maximum load is at most K (i.e., S \leq K), output
No.
Constraints
- 1 \leq M \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- 1 \leq K \leq 10^{15}
- All input values are integers.
Input
N M K A_1 A_2 \ldots A_N
- The first line contains the integer N representing the number of packages, the integer M representing the number of trucks, and the integer K representing the threshold value for the determination, separated by spaces.
- The second line contains the integers A_1, A_2, \ldots, A_N representing the weight of each package, separated by spaces.
Output
If S > K, output Yes; if S \leq K, output No, on a single line.
Sample Input 1
5 2 10 3 5 2 4 6
Sample Output 1
No
Sample Input 2
5 2 9 3 5 2 4 6
Sample Output 2
Yes
Sample Input 3
10 3 20 4 8 2 5 7 3 6 1 9 5
Sample Output 3
No
Sample Input 4
20 4 50 7 12 3 8 15 6 9 11 4 10 13 2 14 5 8 16 3 7 11 6
Sample Output 4
No
Sample Input 5
3 3 5 5 6 5
Sample Output 5
Yes