thz 的粉刷计划
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
thz 最近准备做个手工，他从仓库里找出来了 $n$ 块宽度均为 $1$ 的木板。
现在他打算给这些木板涂上一样颜色的油漆，看起来漂亮一些。
他把这 $n$ 块木板宽度为 $1$ 的边靠在墙边对齐，依次排成一排，第 $i$ 块木板的长度为 $a_i$
但是 thz 的滚筒宽度却是 $k$，也就是意味着 thz 只能一次性同时给 $k$ 块木板从下往上刷漆
如果滚筒在刷漆的过程中，触及到了木板以外的部分，就会把油漆滴落在家里的各处地方，然后被妈妈一顿胖揍
显然 thz 不希望发生这样的惨剧，但是他又希望能尽可能的给木板涂上油漆，所以他想请你帮帮他
告诉他最多能给多大面积的木板涂上油漆，以及相应最小的刷漆次数
输入格式
输入第一行包含两个正整数 $n,k$，分别表示木板数量以及滚筒宽度输入第二行包含 $n$ 个整数，第 $i$ 个数字表示第 $i$ 块木板的高度 $a_i$
对于 $20\%$ 的数据保证：$n \leq 10, k \leq 10$
对于 $50\%$ 的数据保证：$n \leq 10^3, k \leq min(10, n)$
对于 $75\%$ 的数据保证：$n \leq 10^3, k \leq n$
对于 $100\%$ 的数据保证：$n \leq 2 * 10^5, k \leq n, 1 \leq a_i \leq 10^9$
输出格式
输出两行各一个整数，第一行表示最多能涂上油漆的面积
第二行表示最少的刷漆次数
样例
5 2
1 2 4 2 39
3
提示
三次刷漆区间分别为：$[1,2], [2,3], [4,5]$
20240324提高组班级模拟赛
- 状态
- 已结束
- 规则
- IOI
- 题目
- 3
- 开始于
- 2024-3-24 11:30
- 结束于
- 2024-4-3 11:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 9
