/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
円形のケーキがあり、ケーキは切り目によって N 個のピースに分けられています。各切り目は円の中心と円弧上の点を結ぶ線分です。
ピースおよび切り目には時計回りに 1, 2, \ldots, N の番号が付けられており、ピース i の質量は A_i です。ピース 1 をピース N + 1 とも呼ぶこととします。
切り目 i は ピース i とピース i + 1 の間にあり、ピース 1, 切り目 1, ピース 2, 切り目 2, \ldots, ピース N, 切り目 N の順に時計回りに並んでいます。
このケーキを以下の条件を満たすように K 人に分けようとしています。ただし、i 番目の人が受け取るピースの質量の合計を w_i とします。
- すべての人が 1 つ以上の連続するピースを受け取る
- 誰も受け取らないピースは存在しない
- 上の 2 つの条件を満たすという条件下で \min(w_1, w_2, \ldots, w_K) が最大になるようにする
条件を満たす分け方における \min(w_1, w_2, \ldots, w_K) の値および条件を満たすすべての分け方で切られることのない切り目の個数を求めてください。ただし、切り目 i が切られるとは、ピース i とピース i + 1 が異なる人に分けられることを指します。
制約
- 2 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^4
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
条件を満たす分け方における \min(w_1, w_2, \ldots, w_K) の値を x、 切られることのない切り目の個数を y として、x と y をこの順に空白区切りで出力せよ。
入力例 1
5 2 3 6 8 6 4
出力例 1
13 1
以下の分け方が条件を満たします。
- 一方の人にピース 2, 3 を渡し、もう一方の人にピース 4, 5, 1 を渡す。ピース 2, 3 の質量の合計は 14、ピース 4, 5, 1 の質量の合計は 13 である。
- 一方の人にピース 3, 4 を渡し、もう一方の人にピース 5, 1, 2 を渡す。ピース 3, 4 の質量の合計は 14、ピース 5, 1, 2 の質量の合計は 13 である。
条件を満たす分け方における \min(w_1, w_2) の値は 13 であり、どちらの分け方でも切られない切り目は切り目 5 の 1 つです。
入力例 2
6 3 4 7 11 3 9 2
出力例 2
11 1
入力例 3
10 3 2 9 8 1 7 9 1 3 5 8
出力例 3
17 4
Score : 575 points
Problem Statement
There is a circular cake divided into N pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.
The pieces and cut lines are numbered 1, 2, \ldots, N in clockwise order, and piece i has a mass of A_i. Piece 1 is also called piece N + 1.
Cut line i is between pieces i and i + 1, and they are arranged clockwise in this order: piece 1, cut line 1, piece 2, cut line 2, \ldots, piece N, cut line N.
We want to divide this cake among K people under the following conditions. Let w_i be the sum of the masses of the pieces received by the i-th person.
- Each person receives one or more consecutive pieces.
- There are no pieces that no one receives.
- Under the above two conditions, \min(w_1, w_2, \ldots, w_K) is maximized.
Find the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line i is considered cut if pieces i and i + 1 are given to different people.
Constraints
- 2 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^4
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Let x be the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and y be the number of cut lines that are never cut. Print x and y in this order, separated by a space.
Sample Input 1
5 2 3 6 8 6 4
Sample Output 1
13 1
The following divisions satisfy the conditions:
- Give pieces 2, 3 to one person and pieces 4, 5, 1 to the other. Pieces 2, 3 have a total mass of 14, and pieces 4, 5, 1 have a total mass of 13.
- Give pieces 3, 4 to one person and pieces 5, 1, 2 to the other. Pieces 3, 4 have a total mass of 14, and pieces 5, 1, 2 have a total mass of 13.
The value of \min(w_1, w_2) in divisions satisfying the conditions is 13, and there is one cut line that is not cut in either division: cut line 5.
Sample Input 2
6 3 4 7 11 3 9 2
Sample Output 2
11 1
Sample Input 3
10 3 2 9 8 1 7 9 1 3 5 8
Sample Output 3
17 4