小明的喷涂计划——高级
3 Sec 64 MB |
7 | 11 |
通过 | 提交 |
题目描述
小明有一段破旧的围栏要喷涂。围栏由N个木板构成,每个宽度都为1cm,但是高度各不相同。这个任务非常简单,他给自己买了一个喷漆机器,喷涂头有Xcm宽。
小明的喷漆机器是直接喷射的,因此喷头的每一个部位必须一直接触到木板,否则尤其会污染他的农田。并且机器也必须时刻与地面平行。可以看出,小明必须同时对X个木板同时喷涂,且从底部到达最短的那个木板。然后再选择连续的X个……
由于机器的特殊性,有可能有部分木板没有被喷涂。小明希望这样的木板面积最少,并且喷涂的次数尽量的少。
输入格式
第一行两个整数N(1<=N<=1,000,000),表示木板个数,以及X(1<=X<=100,000)表示碰头宽度。喷头宽度不会超过围栏的宽度。
第二行N个正整数,表示每个木板的高度,并且都不超过1,000,000。
输出格式
最少的未喷涂面积,以及最少的喷涂次数。
样例输入 #1
5 3 5 3 4 4 5 10 3 3 3 3 3 3 3 3 3 3 3 7 4 1 2 3 4 3 2 1
样例输出 #1
3 2 0 4 4 4