2023 蓝桥杯热身赛

Problem P26. 数列分段

HZC 早闻 LWH 对数学研究颇深,于是带着以下问题去考他:对于给定的一个长度为N的正整数数列 A,现要将其分成 M 段,并要求每段连续,且每段和的最大值最小。

例如,将数列 [4, 2, 4, 5, 1] 要分成 3 段:

若分为 [4, 2][4, 5][1],各段的和分别为 6, 9, 1,和的最大值为 9

若分为 [4][2, 4][5, 1],各段的和分别为 4, 6, 6,和的最大值为 6

并且无论如何分段,最大值不会小于 6,所以可以得到要将数列 [4, 2, 4, 5, 1] 要分成 3 段,每段和的最大值最小为 6

然而,LWH 只是外强中干,他开始虚了,现在请你帮他编程解决这个问题。

输入

1 行包含两个正整数 N, M \ (1 \leq M \leq N \leq 10^5)

2 行包含 N 个空格隔开的非负整数 a_1,a_2,...,a_N \ (1 \leq a_i \leq 10^9),表示数列各项的值。

输入保证 \sum_{i=1}^N{a_i} \leq 10^9

输出

输出仅包含一个正整数,表示每段和最小的最大值。

样例

标准输入 复制文本
5 3
4 2 4 5 1
标准输出 复制文本
6

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 7
通过 3