#360. 数列分段 II

数列分段 II

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于给定的一个长度为 N\red{N} 的正整数数列 A\red{A} ,现要将其分成 M\red{M} 段,并要求每段连续,且每段和的最大值最小。

例如,将数列4  2  4  5  1\red{ 4 \ \ 2 \ \ 4 \ \ 5 \ \ 1} 要分成 3\red{3} 段:

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

若分为 [4][2 4][5 1]\red{[4][2~ 4][5~ 1]},各段的和分别为 4,6,6\red{4, 6, 6} ,和的最大值为 6\red{6}

并且无论如何分段,最大值不会小于 6\red{6}

所以可以得到要将数列 4  2  4  5  1\red{4 \ \ 2 \ \ 4 \ \ 5 \ \ 1} 要分成 3\red{3} 段,每段和的最大值最小为 6\red{6}

输入格式

1\red{1} 行包含两个正整数 N\red{N}M\red{M}

2\red{2} 行包含 N\red{N} 个空格隔开的非负整数 Ai\red{A_i},含义如题目所述。

输出格式

仅包含一个正整数,即每段和最大值最小为多少。

样例

输入样例

5 3
4 2 4 5 1

输出样例

6

提示

对于 20%\red{20\%}的数据,有 N10\red{N \leq 10}

对于 40%\red{40\%}的数据,有 N1000\red{N \leq 1000}

对于 100%\red{100\%}的数据,有 N105MN\red{N \leq 10^5,M \leq N}Ai\red{A_i} 之和不超过 109\red{10^9}

寒假营高级班测试

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2022-1-13 14:00
结束于
2022-1-14 14:00
持续时间
24 小时
主持人
参赛人数
10