103705: [Atcoder]ABC370 F - Cake Division
Description
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
Output
得分：575分
问题陈述
有一个圆形蛋糕，被N条切线分成了N块。每条切线都是连接圆心到圆弧上一点的线段。
块和切线按顺时针方向编号为1, 2, …, N，第i块的质量为A_i。第1块也可以称为第N + 1块。
第i条切线位于第i块和第i + 1块之间，它们按顺时针顺序排列：第1块，第1条切线，第2块，第2条切线，…，第N块，第N条切线。
我们想要在以下条件下将这块蛋糕分给K个人。设w_i是第i个人收到的蛋糕块的总质量。
- 每个人收到一个或多个连续的块。
- 没有蛋糕块是无人接收的。
- 在上述两个条件下，最大化$\min(w_1, w_2, \ldots, w_K)$。
找出满足条件的分配中$\min(w_1, w_2, \ldots, w_K)$的值，以及满足条件的分配中从未被切割的切线数量。这里，如果第i块和第i + 1块被分给不同的人，则第i条切线被认为是被切割的。
约束条件
- $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$
输出
设$x$为满足条件的分配中$\min(w_1, w_2, \ldots, w_K)$的值，$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条切线。
样本输入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