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)

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

Info

NOJ

Provider NOJ

Code NOJ1568

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet