bzoj#P1979. [SPOJ685] SEQPAR

[SPOJ685] SEQPAR

题目描述

有一个长度为 nn 的整数序列 a1ana_1 \ldots a_naia_i 可以为负数)。将它们分成正好 mm 段。设第 ii 段的子序列和为 sis_ii[1,m]i \in [1, m])。求一个拆分方法,使 maxi=1m{si}\max_{i=1}^m\{s_i\} 最小。

输入格式

第一行两个整数 n,mn, m

接下来 nn 个整数,代表 a1ana_1 \ldots a_n

输出格式

输出一个数,代表 maxi=1m{si}\max_{i=1}^m\{s_i\}

6 3
150
-50
1
101
1
100
101

数据规模与约定

对于 100%100\% 的数据,1mn1041 \le m \le n \le 10^4104ai104-10^4 \le a_i \le 10^4