分数: 575 点
问题陈述
有一个圆形蛋糕分为 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 和 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
输出
让 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