CPC '19 Contest 1 P2 - Luggage - DMOJ: Modern 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 \leq h_{i}, K \leq 10^{9}$

Subtask 1 [10%]

$1 \le N \le 20$ $1 \leq N \leq 20$

Subtask 2 [15%]

$1 \le N \le 2 \times 10^3$ $1 \leq N \leq 2 \times 10^{3}$

Subtask 3 [75%]

$1 \le N \le 2 \times 10^5$ $1 \leq N \leq 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

Copy

5 3
25 9 1 6 8

Sample Output

Copy

Sample Explanation

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

Comments

2

VectorGraphicz commented 11 days ago ← edited →

"Output the most amount of items"

erm actually 🤓🤓🤓 … it's "number" of items because items are countable 🤓🤓🤓

4

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

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