Boats for Two

Difficulty: 1400 3500 ms 128 MB

greedy two-pointers

Each boat carries at most two people and at most C total weight; everyone's weight is at most C. What is the minimum number of boats?

Input: the first line has N and C; the second line has N weights.

Output: the minimum number of boats.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ w_i ≤ C ≤ 2×10⁴

Sample Tests

4 5
1 2 3 5

3

2 3
3 3

2

Read the Editorial