#P1158. 「一本通 1.2 练习 1」数列分段 II

    Type: Default 1000ms 256MiB

「一本通 1.2 练习 1」数列分段 II

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

对于给定的一个长度为 NN 的正整数数列 AA ,现要将其分成 MM 段,并要求每段连续,且每段和的最大值最小。

例如,将数列 4  2  4  5  14 \ \ 2 \ \ 4 \ \ 5 \ \ 1 要分成 33 段:

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

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

并且无论如何分段,最大值不会小于 66

所以可以得到要将数列 4  2  4  5  14 \ \ 2 \ \ 4 \ \ 5 \ \ 1 要分成 33 段,每段和的最大值最小为 66

输入格式

11 行包含两个正整数 NNMM

22 行包含 NN 个空格隔开的非负整数 AiA_i,含义如题目所述。

输出格式

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

样例

5 3
4 2 4 5 1
6

数据范围与提示

对于 20%20\%的数据,有 N10N \leq 10

对于 40%40\% 的数据,有 N1000N \leq 1000

对于 100%100\%的数据,有 N105N \leq 10^5MNM \leq NAiA_i 之和不超过 10910^9

测验

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2022-8-16 19:30
End at
2022-8-16 21:30
Duration
2 hour(s)
Host
Partic.
2