问题 2196. -- 最佳牛围栏 Best Cow Fence

2196: 最佳牛围栏 Best Cow Fence

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 3
[提交][状态][讨论版]

题目描述

农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入

第一行输入整数 N 和 F ,数据间用空格隔开。
接下来 N 行,每行输入一个整数,第i+1行输入的整数代表第i片区域内包含的牛的数目。

输出

输出一个整数,表示平均值的最大值乘以1000再 向下取整 之后得到的结果。

样例输入

10 6
6 
4
2
10
3
8
5
9
4
1

样例输出

6500

提示

数据范围:1≤N≤100000,1≤F≤N

来源

[提交][状态]