Boxes Packing
Contest: Codeforces Round 515 (Div. 3)
Difficulty rating: 1800
Tags: binary search, implementation

Maksim has $$$n$$$ objects and $$$m$$$ boxes, each box has size exactly $$$k$$$. Objects are numbered from $$$1$$$ to $$$n$$$ in order from left to right, the size of the $$$i$$$-th object is $$$a_i$$$.

Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the $$$i$$$-th object fits in the current box (the remaining size of the box is greater than or equal to $$$a_i$$$), he puts it in the box, and the remaining size of the box decreases by $$$a_i$$$. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.

Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.

Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).

Input format:
The first line of the input contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the number of objects, the number of boxes and the size of each box.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$), where $$$a_i$$$ is the size of the $$$i$$$-th object.

Output format:
Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example Maksim can pack only $$$4$$$ objects. Firstly, he tries to pack all the $$$5$$$ objects. Distribution of objects will be $$$[5], [2, 1]$$$. Maxim cannot pack the next object in the second box and he has no more empty boxes at all. Next he will throw out the first object and the objects distribution will be $$$[2, 1], [4, 2]$$$. So the answer is $$$4$$$.

In the second example it is obvious that Maksim cannot pack all the objects starting from first, second, third and fourth (in all these cases the distribution of objects is $$$[4]$$$), but he can pack the last object ($$$[1]$$$).

In the third example Maksim can pack all the objects he has. The distribution will be $$$[1, 2], [3], [1, 1]$$$.

Example input:
5 2 6
5 2 1 4 2

Example output:
4

Example input:
5 1 4
4 2 3 4 1

Example output:
1

Editorial:
The first solution is some kind of a straight-forward understanding the problem. Let's do binary search on the answer. So our problem is to find the smallest $$$x$$$ such that the suffix of the array $$$a$$$ starting from the position $$$x$$$ can be packed in boxes. It is easy to see that if we can do it for some $$$x$$$ then we always can do it for $$$x+1$$$. And to find the answer for the fixed $$$x$$$ we have to simulate the process described in the problem statement starting from the position $$$x$$$. Okay, this is $$$O(n \log n)$$$ solution.
The second solution is more interesting than the first one. The approach is to reverse the initial array, simulate the process from the first position of reversed array and then all the objects we can pack are in the best answer and there is no better answer at all.
Why it works?
Let's take a look on the last box in the best answer if we will go from left to right in the initial array. Let objects in this box be $$$a_{lst_1}, a_{lst_2}, \dots, a_{lst_x}$$$. What do we see? $$$\sum\limits_{i = 1}^{x}a_{lst_i} \le k$$$. So all these objects are fit in the last box (obviously). Now if we will iterate over objects from right to left, these objects will fit also! It means that we cannot do worse by such a transform (reversing) at least for the last box.
But what will happen if we can put some of the previous objects in this box? Well, it will not make worse for this box, but what about next boxes (previous boxes in straight notation)? Let objects in the penultimate box be $$$a_{prev_1}, a_{prev_2}, \dots, a_{prev_y}}$$$. What do we see? These objects are fit in this box (obviously again). What will happen if we will put in the last box one or more objects of this box? Then the left border of objects which we will put in it will not increase because we decrease the number of object in this box. So we can see that for previous boxes this condition is also satisfied.
So we can solve the problem with this approach. Time complexity of this solution is $$$O(n)$$$.