← 返回题目列表

AtCoder · abc370_f

I. 蛋糕事业部

中文机器翻译题面 查看原题

分数: 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