普及⏱ 1000ms💾 256MB#P5071

题目描述

把数组按原顺序分成 $m$ 段非空连续子数组,最小化"最大段和",输出这个最小值。(数据保证可行:每段至少一个元素。)

输入格式

第一行两个整数 $n$$m$;第二行 $n$ 个整数。

输出格式

一行一个整数。

数据范围

$$m \le n \le 10^5,\ |a_i| \le 10^4$$

样例输入 #1
1 1
-5
样例输出 #1
-5
样例输入 #2
5 1
1 2 3 4 5
样例输出 #2
15