1442: 环形畜棚4

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:38 通过:16

题目描述

农夫约翰对现代建筑学非常感兴趣,于是他把他的畜棚连起来建成了一个完美的圆形,每个畜棚代表一个房间,总共有n个房间(顺时针编号从1n)。每个房间都有一扇可以通向相邻两个房间的门(内门),同时,每个房间也各有一扇通向外面的门(外门)。

约翰想让第i个房间有ri头奶牛,为了达到这个目的,他一开始的时候打开了k扇外门允许奶牛进入,每头奶牛进入外门以后都将沿着顺时针方向通过内门走到各自合适的终点房间里去。约翰知道,这k扇门开在不同的位置,会对所有奶牛最后走的总路程的大小产生影响。每头奶牛行走的路程就是其通过内门的数量,所有奶牛的总路程就是每头奶牛路程的总和。

现在,请你来计算所有奶牛需要走的最小总路程。

输入格式

输入文件第一行是两个正整数nk,表示有n个房间和可以打开k扇外门,接下来n行(顺时针方向),每行一个整数ri表示最后第i个房间需要有ri头奶牛。

输出格式

输出文件只有一行一个整数,表示所有奶牛需要走的最小总路程。

输入样例 复制

6 2
2
5
4
2
6
2

输出样例 复制

14

数据范围与提示

【输入输出样例1说明】

如果把两扇外门开在第2个和第5个房间,那么11头奶牛进入第2个房间,总共需要路程8走到各自的房间,10头奶牛从第5个房间进入,需要花费的总路程是6才能走到各自的房间。

【数据说明】

3<=n<=1001<=k<=71<=ri<=1000000