← 返回题目列表

Codeforces · 1070/D

D. 垃圾处理

中文机器翻译题面 查看原题

够了。瓦夏经常忘记倒垃圾,导致他的公寓散发出恶臭。现在他想制定一个垃圾处理计划并坚持下去。

对于接下来的 $$$n$$$ 天,Vasya 知道 $$$a_i$$$ — 他将在第 $$$i$$$ 天产生的垃圾单位数。每个单位的垃圾必须在产生当天或第二天进行处理。 Vasya 处理垃圾的方法是将垃圾放入袋子中,然后将袋子放入垃圾箱中。每个袋子最多可容纳 $$$k$$$ 单位的垃圾。一天内可以将多个袋子组合并放入垃圾箱中。

为了节省开支,Vasya 希望使用尽可能少的袋子。您需要计算 Vasya 在给定的 $$$n$$$ 天数内需要处理其所有垃圾的最少袋子数量。第 $$$n$$$ 天后不应留下任何垃圾。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le k \le 10^9$$$) — 要考虑的天数和行李的容量。第二行包含 $$$n$$$ 空格分隔的整数 $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — 第 $$$i$$$ 天产生的垃圾单位数。

输出

输出一个整数——Vasya 需要处理所有垃圾的最小袋子数。每单位垃圾应在产生当日或次日进行处理。第 $$$n$$$ 天后不能留下任何垃圾。一天之内可以放置和投放多个行李。

示例

输入 #1

3 2
3 2 1

输出 #1

3

输入 #2

5 1
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #2

5000000000

输入 #3

3 2
1 0 1

输出 #3

2

输入#4

4 4
2 8 4 1

输出#4

4