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

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ ¡ ¢ £ ¤ ¥ ¦ §

Type: Default

1000ms

256MiB

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.

题目描述

对于给定的一个长度为 $N$ 的正整数数列 $A$ ，现要将其分成 $M$ 段，并要求每段连续，且每段和的最大值最小。

例如，将数列 $4 \ \ 2 \ \ 4 \ \ 5 \ \ 1$ 要分成 $3$ 段：

若分为 $[4$ $2][4$ $5][1]$ ，各段的和分别为 $6, 9, 1$ ，和的最大值为 $9$ ；

若分为 $[4][2$ $4][5$ $1]$ ，各段的和分别为 $4, 6, 6$ ，和的最大值为 $6$ ；

并且无论如何分段，最大值不会小于 $6$ 。

所以可以得到要将数列 $4 \ \ 2 \ \ 4 \ \ 5 \ \ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$ 。

输入格式

第 $1$ 行包含两个正整数 $N$ ， $M$ ；

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$ ，含义如题目所述。

输出格式

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

样例

5 3
4 2 4 5 1

数据范围与提示

对于 $20\%$ 的数据，有 $N \leq 10$ ；

对于 $40\%$ 的数据，有 $N \leq 1000$ ；

对于 $100\%$ 的数据，有 $N \leq 10^5$ ， $M \leq N$ ， $A_i$ 之和不超过 $10^9$ 。

第七届SWPU-ACM新生预选赛

Not Attended

Status: Done
Rule: ACM/ICPC
Problem: 103
Start at: 2022-9-19 14:00
End at: 2022-10-28 14:00
Duration: 936 hour(s)
Host: oyf
Partic.: 58

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

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

题目描述

输入格式

输出格式

样例

数据范围与提示

第七届SWPU-ACM新生预选赛

Status

Development

Support

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

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

题目描述

输入格式

输出格式

样例

数据范围与提示

第七届SWPU-ACM新生预选赛

Status

Development

Support

Don't have an account?

SIGN IN