← 返回题目列表

Codeforces · 1066/D

D. 盒子包装

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

Maksim 有 $$$n$$$ 对象和 $$$m$$$ 盒子,每个盒子的大小恰好为 $$$k$$$。对象按从左到右的顺序从$$$1$$$到$$$n$$$编号,第$$$i$$$个对象的大小为$$$a_i$$$。

Maksim 想要将他的物体装入盒子中,他将通过以下算法打包物体:他取出他拥有的一个空盒子,从左到右遍历物体,如果第 $$$i$$$ 个物体适合当前盒子(盒子的剩余大小大于或等于 $$$a_i$$$),则将其放入盒子中,盒子的剩余大小减少$$$a_i$$$。否则,他会取出新的空盒子并继续上述过程。如果他没有空盒子,并且某个盒子中至少有一个物体不在,那么马克西姆就无法打包所选的一组物体。

Maksim 想知道他可以通过上述算法打包的最大物体数量。为了达到这个目标,他会扔掉该组中最左边的物体,直到剩下的一组物体可以装进他拥有的盒子里。你的任务是说出马克西姆可以装进他拥有的盒子里的最大物品数量。

每次当 Maksim 尝试将物体装入盒子时,他都会清空之前拥有的所有盒子(并且剩余物体组的相对顺序不会改变)。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — 对象的数量、盒子的数量以及每个盒子的大小。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个对象的大小。

输出

使用问题陈述中描述的算法打印 Maksim 可以打包的最大对象数。

示例

输入 #1

5 2 6
5 2 1 4 2

输出 #1

4

输入 #2

5 1 4
4 2 3 4 1

输出 #2

1

输入 #3

5 3 3
1 2 3 1 1

输出 #3

5

注意

在第一个示例中,Maksim 只能打包 $$$4$$$ 对象。首先,他尝试打包所有 $$$5$$$ 物品。对象的分布将为$$$[5], [2, 1]$$$。马克西姆无法将下一个物品放入第二个盒子中,并且他根本没有更多的空盒子。接下来,他将抛出第一个对象,对象分布将为 $$$[2, 1], [4, 2]$$$。所以答案是$$$4$$$。

在第二个例子中,很明显,Maksim 无法打包从第一、第二、第三和第四开始的所有对象(在所有这些情况下,对象的分布都是 $$$[4]$$$),但他可以打包最后一个对象($$$[1]$$$)。

在第三个示例中,Maksim 可以打包他拥有的所有对象。分布将为 $$$[1, 2], [3], [1, 1]$$$。