DMPG '18 B6 - House of Cards

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Mimi is building a house of cards! However, being the strange person that she is, she has N premade layers of cards, with width 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 is stack on top of layer B, the width of layer A must be at least K less than 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 K \le 1\,000\,000
1 \le w_i \le 1\,000\,000

Subtask 2 [80%]

1 \le N \le 2\,000
1 \le K \le 1\,000\,000
1 \le w_i \le 1\,000\,000

Input Specification

The first line will have two space separated integers, N and K.
The next line will have N space separated integers, w_1, w_2, w_3, \ldots, 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

4

Comments


  • 0
    echofox  commented on April 25, 2018, 9:37 p.m.

    nice meme