Cake Division

题目描述

有一个圆形蛋糕被切线分成 $N$ 块。每条切线是连接圆心到弧上一点的线段。 这些块和切线按顺时针方向编号为 $1, 2, \ldots, N$，且第 $i$ 块的质量为 $A_i$。第 $1$ 块也被称为第 $N + 1$ 块。 切线 $i$ 在第 $i$ 块和第 $i + 1$ 块之间，并且它们按顺时针顺序排列为：第 $1$ 块、切线 $1$、第 $2$ 块、切线 $2$、$\ldots$、第 $N$ 块、切线 $N$。 我们想在以下条件下把这个蛋糕分给 $K$ 个人。令 $w_i$ 为第 $i$ 个得到的人的所获块的质量之和。

每个人都得到一个或多个 连续 的块。 没有块是无人得到的。 在上述两个条件下，使得 $\min(w_1, w_2, \ldots, w_K)$ 最大化。

求在满足条件的划分中 $\min(w_1, w_2, \ldots, w_K)$ 的值，以及在满足条件的划分中从未被切开的切线的数量。在此，如果第 $i$ 条切线的两边的块被分给不同的人，则认为切线 $i$ 被切开。

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设 $x$ 为在满足条件的划分中 $\min(w_1, w_2, \ldots, w_K)$ 的值，$y$ 为从未被切开的切线的数量。按此顺序输出 $x$ 和 $y$，用一个空格分隔。

5 2
3 6 8 6 4

13 1

6 3
4 7 11 3 9 2

11 1

10 3
2 9 8 1 7 9 1 3 5 8

17 4

提示

$2 \leq K \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq 10^4$ 所有输入值均为整数。以下划分满足条件：

把第 $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$。

标签: AtCoder|abc370F

来源

AtCoder|abc370F