#P1979. Spoj685 Seqpar

    ID: 1002 传统题 1000ms 162MiB 尝试: 149 已通过: 50 难度: 7 上传者: 标签>CF2200提高线性 DP一维前缀和离散化树状数组二分查找滚动数组

Spoj685 Seqpar

题目描述

有一个长度为 nn 的整数序列 a1…ana_1 \ldots a_n(aia_i 可以为负数)。将它们分成正好 mm 段。设第 ii 段的子序列和为 sis_i(i∈[1,m]i \in [1, m])。求一个拆分方法,使 max⁡i=1m{si}\max_{i=1}^m\{s_i\} 最小。

输入格式

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

接下来 nn 个整数,代表 a1…ana_1 \ldots a_n。

输出格式

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

6 3
150
-50
1
101
1
100
101

数据规模与约定

对于 100%100\% 的数据,1≤m≤n≤1041 \le m \le n \le 10^4,−104≤ai≤104-10^4 \le a_i \le 10^4。