均匀分段

题目描述

给定 $N$ 个整数组成一个序列 $A_1,A_2,\cdots, A_N$，请设计一种划分方法，能将它们分割成 $M$ 段（每段都应该是连续的），且各片段数字之和的最大值达到最小，输出这个最小值。

输入格式

• 第一行：两个整数 $N$ 与 $M$；
• 第二行：$N$ 个整数 $A_1,A_2,\cdots,A_N$。

输出格式

• 单个整数：表示最大段之和的最小值

数据范围

• 对于 $30\%$ 的数据 $1 \leq n \leq 100$；
• 对于 $60\%$ 的数据 $1 \leq n \leq 5000$；
• 对于 $100\%$ 的数据 $1 \leq n \leq 200,000$；
• $1 \leq a_i \leq 10000$，$1 \leq m \leq n$。

样例输入 #1

4 2
10 20 30 40

样例输出 #1

60

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布