CPC '19 Contest 1 P2 - Luggage - Olympiads Online Judge

CPC '19 Contest 1 P2 - Luggage

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

Angie is going on vacation!

But she has too much stuff she wants to bring! She has $N$ ~N~ items, each with a height of $h_i$ ~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$ ~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?

Constraints

For all subtasks:

$1 \le h_i, K \le 10^9$ ~1 \le h_i, K \le 10^9~

Subtask 1 [10%]

$1 \le N \le 20$ ~1 \le N \le 20~

Subtask 2 [15%]

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

Subtask 3 [75%]

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

Input Specification

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

The second line of input contains $N$ ~N~ space separated integers $h_1, h_2, \dots, h_N$ ~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$ ~2~, $4$ ~4~, and $5$ ~5~ for a height range of $3$ ~3~.

Comments

0

ev_code commented on Oct. 21, 2024, 5:17 p.m. ← edited →

Imagine wanting to bring $2 × 10^5$ ~2 × 10^5~ items with heights ranging from $1$ ~1~ to $10^9$ ~10^9~ on vacation 🤯