#G0081. RW捡垃圾【2025期末考试T3】

RW捡垃圾【2025期末考试T3】

题目描述

RW是个粗心的人,经常不小心把垃圾丢到地上。AQX实在没办法,只好派了mm个学生,去捡RW走过路上的垃圾。

假设RW走过的路线是一条直线,每个位置分别是1,2,...,n1,2,...,n,每个位置上垃圾的个数是aia_i。所有学生起始位置都在00,每秒钟,他们有两种选择:

1.向右走一步。

2.捡起一个地上的垃圾。

现在我们的问题是:要捡起RW的所有垃圾,最少需要多少秒?

输入格式

第一行输入两个正整数n,mn,m,如题目所述。

第二行输入nn个非负整数aia_i,代表每个位置的垃圾个数。ai109a_i\leq 10^9

输出格式

一个数字,表示最少的时间。

样例输入1

3 2
1 0 2

样例输出1

5

样例解释

第一个学生走到位置33,把这里的两个垃圾都捡起来,一共花费55秒。第二个学生走到11,把这里的垃圾捡起来,花费22秒。两个学生可以同步操作,所以最终的时间是55秒。

大样例在此

数据分布

对于30%的数据,m=1m=1

对于另30%的数据,m=2m=2,垃圾总个数21\leq 21

对于100%的数据,n,m100000n,m\leq 1000000ai1090\leq a_i \leq 10^9,保证至少一共有一个垃圾。