CBOJ Winter Contest Problem 2 - Suitcase Packing (Hard)


Submit solution

Points: 10
Time limit: 0.5s
Memory limit: 512M

Author:
Problem type

Note: This problem originated from the CBOJ Winter Contest and is updated with larger constraints.

Bob is dreaming about going on vacation, but before he embarks on his journey, he must pack his bags!

Bob's airport enforces a weight limit of \(W\) kilograms for each suitcase. Bob can pack as many suitcases as he wants, as long as none of them hold items that exceed \(W\) kilograms when added up. As Bob's items are rather bulky, he can only pack a maximum of 2 things into 1 suitcase.

Given a list of \(N\) items Bob wishes to bring, find the minimum number of suitcases Bob needs to carry all his things, with each suitcase being within weight limit!

Input Specification

The first line contains two integer \(N\) and \(W\) \((1 \le N \le 2 \times 10^5, 1 \le W \le 10^9)\), representing the number of items Bob wants to bring and the airport's suitcase weight limit.

The next line contains \(N\) integers with values ranging from \(1\) to \(W\) inclusive, with the \(i\)-th element describing the \(i\)-th item's weight in kilograms.

Note that the weight limit will always be greater than or equal to the heaviest item Bob is planning to pack.

Output Specification

Output an integer, indicating the minimum number of suitcases Bob needs.

Sample Input

4 5
1 2 3 3

Sample Output

2

Sample Explanation

Bob can pair the items \((1, 3)\) and \((2, 3)\) together, forming suitcases with weights of 4kg and 5kg respectively.


Comments

There are no comments at the moment.