网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1192. -- 锘爷考驾照

1192: 锘爷考驾照

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

题目描述

大家都知道,锘爷是XDUdp第一人,所以锘爷决定要去考驾照!(这很有逻辑吧),他为了一次考到驾照,于是买了一辆越野车从学校开回家来练习开车,在途中就会有很多高山和低谷(低谷可能比地平面低)。经过一段时间的调查,现在他已经知道了最短的路线,我们假设这是一条直线,并且他一定会走这条直线。但是这也太远了,锘爷想找一段开车的时间打瞌睡,为了更舒服的打瞌睡,于是锘爷统计了这条路线上所有的山峰和谷底的高度,他想知道长度为length的路上高度之和最小的一段是多少?

输入

多组数据(不超过50组),处理到文件结束。
对于每组数据,读入一个整数n,length(1<=length<=n<=200000)n表示山峰和低谷数,length表示诺爷打瞌睡的长度。
接下来是n个整数h(i),表示高度,abs(h(i))<=200000。

输出

对于每组数据,输出一个整数表示长度为length高度和的最小值。

样例输入

3 2
1 2 3
5 3
1 -1 -1 2 -5

样例输出

3
-4

提示

来源

[提交][状态][讨论版]