CodeForces - 1066D Boxes Packing 没做出来 题意 思维

D. Boxes Packing

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Maksim has nn objects and mm boxes, each box has size exactly kk. Objects are numbered from 11 to nn in order from left to right, the size of the ii-th object is aiai.

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 ii-th object fits in the current box (the remaining size of the box is greater than or equal to aiai), he puts it in the box, and the remaining size of the box decreases by aiai. 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

The first line of the input contains three integers nn, mm, kk (1≤n,m≤2⋅1051≤n,m≤2⋅105, 1≤k≤1091≤k≤109) — the number of objects, the number of boxes and the size of each box.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤k1≤ai≤k), where aiai is the size of the ii-th object.

Output

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

Examples

input

Copy

5 2 6 5 2 1 4 2

output

Copy

4

input

Copy

5 1 4 4 2 3 4 1

output

Copy

1

input

Copy

5 3 3 1 2 3 1 1

output

Copy

5

Note

In the first example Maksim can pack only 44 objects. Firstly, he tries to pack all the 55 objects. Distribution of objects will be [5],[2,1][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][2,1],[4,2]. So the answer is 44.

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][4]), but he can pack the last object ([1][1]).

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

分析：

当时题意未懂，正着模拟没做出来，

题意：

有n个物品，、第一给物品开始往右边挑选，对于每一个物品，如果可以放得下的就直接放进盒子，若目前的盒子放不下,那就要另外开一个盒子来放物品了，若目前还有可用的盒子，那就继续选取下去，若目前已经没有可用的盒子了，说明这次选取是不对的，那么选取的第一个物品退回去，看是否有剩余的空间放下该物品，如果还是放不下的话，继续把第二个拿的物品退回去，直至可以放下该物品为止，然后继续选取下去。

求最多可以挑选出多少物品，

我们发现他最后一个物品是一定要放进去的，我们可以逆着放。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define N 100100 
typedef long long ll;
long long n,m,v,a[N];
int main()
{

    
     while(scanf("%lld%lld%lld",&n,&m,&v)!=EOF)  
    {  
         long long sum=0;
         long long ans=0;
         for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]) ;
        }
        ll t=v;
        for(int i=n;i>=1;i--)
        {
              if(a[i]<=t)
              {
                t-=a[i];
                ans++;
              }
              else
              {
                m--;
                if(m==0) break;
                t=v;
                t-=a[i];
                ans++;
              }
        }
        printf("%lld\n",ans);
    }  

      
    return 0;
}