DMPG '18 B6 - House of Cards - Olympiads Online Judge

DMPG '18 B6 - House of Cards

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Kirito

Problem type

Mimi is building a house of cards! However, being the strange person that she is, she has $N$ ~N~ premade layers of cards, with width $w_i$ ~w_i~.

Mimi proceeds to build a house of cards by stacking the layers of cards, one on top of another. However, she realizes that people will become suspicious if the layers are too similar in width, or if the stack grows wider as it gets taller. Thus if layer $A$ ~A~ is stack on top of layer $B$ ~B~, the width of layer $A$ ~A~ must be at least $K$ ~K~ less than $B$ ~B~.

Given these constraints, what is the tallest house of cards Mimi can make?

Constraints

Subtask 1 [20%]

$1 \le N \le 8$ ~1 \le N \le 8~
$1 \le K \le 10^9$ ~1 \le K \le 10^9~
$1 \le w_i \le 10^9$ ~1 \le w_i \le 10^9~

Subtask 2 [80%]

$1 \le N \le 2\,000$ ~1 \le N \le 2\,000~
$1 \le K \le 10^9$ ~1 \le K \le 10^9~
$1 \le w_i \le 10^9$ ~1 \le w_i \le 10^9~

Input Specification

The first line will have two space separated integers, $N$ ~N~ and $K$ ~K~.
The next line will have $N$ ~N~ space separated integers, $w_1, w_2, \dots, w_N$ ~w_1, w_2, \dots, w_N~, the widths of the card layers.

Output Specification

A single integer, the number of layers in the tallest house of cards Mimi can make.

Sample Input

5 4
7 2 20 9 12

Sample Output

Comments

0

echofox commented on April 26, 2018, 1:37 a.m.

nice meme