CPC '19 Contest 1 P2 - Luggage

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Angie is going on vacation!

But she has too much stuff she wants to bring! She has N items, each with a height of h_i. However, her suitcase is quite special, it can fit as many items in it as she wants as long as they have a height range of K or less. The height range is the absolute difference between the maximum height of any item in the suitcase and the minimum height of any item in the suitcase.

Being a logical person, Angie wants to fit as many items in her suitcase as she can. Can you help her figure out how many?


For all subtasks:

1 \le h_i, K \le 10^9

Subtask 1 [10%]

1 \le N \le 20

Subtask 2 [15%]

1 \le N \le 2 \times 10^3

Subtask 3 [75%]

1 \le N \le 2 \times 10^5

Input Specification

The first line contains the space separated integers N and K.

The second line of input contains N space separated integers h_1, h_2, \dots, h_N.

Output Specification

Output the most amount of items Angie can bring in her suitcase.

Sample Input

5 3
25 9 1 6 8

Sample Output


Sample Explanation

She can bring items 2, 4, and 5 for a height range of 3.


There are no comments at the moment.