Diferencia Productiva


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Los concursantes de computación de todo el país, con el objetivo de vincular el estudio con el trabajo, cuentan con un enorme campo dividido en N (1 \leq N \leq 10^5) parcelas de iguales dimensiones. Cada parcela puede ser identificada con un entero positivo que representa su producción total. De esta manera, es posible modelar el campo mediante un conjunto de N enteros positivos P_i (1 \leq P_i \leq 10^9), donde cada elemento representa una parcela.

Debido a complicadas razones de naturaleza técnica, es necesario seleccionar un subconjunto del conjunto original que contenga la mayor cantidad posible de elementos (parcelas), satisfaciendo la restricción de que la diferencia entre el mayor y el menor elemento de dicho subconjunto no sea mayor que un entero positivo D (1 \leq D \leq 10^9) fijado de antemano.

Entrada

• Línea 1: Dos enteros N y D (separados por un espacio en blanco) que representan la cantidad de parcelas y la diferencia máxima permitida respectivamente.

• Líneas 2…N+1: En la línea i+1 aparecerá el valor P_i, que representa el valor de la producción de la \(i-ésima\) parcela.

Salida

En la única línea de la salida escribir un entero que represente la cantidad máxima de parcelas que puede ser seleccionada.

Ejemplo de Entrada

9 10
8
1
100
20
1
50
2
10
1000

Ejemplo de Salida

5

Explicación

Un subconjunto de 5 elementos que cumple la restricción está formado por las producciones {8, 1, 10, 2, 1}. Como no existen subconjuntos con más de 5 elementos que cumplan la restricción, la respuesta es 5.


Comments

There are no comments at the moment.