Preparing NOJ

分礼物

1000ms 65536K

Description:

出去春游一趟回来后,ZZ带回来很多礼物。每个礼物有一个价值。他将所有礼物排成一列,并将这些礼物分成M 份,每一份是由一个或多个礼物组成的连续的序列。他要将这M 份礼物分别送给他的M 个朋友。这样的划分有个要求,那就是使总价值最大的片段的总价值尽量小。

Input:

第一行为两个整数N(1<=N<=100,000),M(1<=M<=N)。接下来N行按顺序给出每个物品的价值v(1<=v<=10,000)

Output:

输出为一个整数,为满足题目条件的最大的连续序列的总价值

Sample Input:

7 5
100
400
300
100
500
101
400

Sample Output:

500

Note:

满足题意的一个划分如下所示:
100 400 300 100 500 101 400
---1--- ---2--- -3- -4- -5-
500 400 500 101 400

本题由旧版NOJ导入,来源:

Info

NOJ

Provider NOJ

Code NOJ1585

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet