#C8770. Maximum Donuts Selection with Freshness Constraint
Maximum Donuts Selection with Freshness Constraint
Maximum Donuts Selection with Freshness Constraint
You are given a set of n donuts, each with a freshness rating. Your task is to select the largest possible subset of donuts such that the difference between the highest and the lowest freshness ratings in the subset is at most d. Formally, for a chosen subset S, the condition is described by the inequality:
\(\max_{x \in S} x - \min_{x \in S} x \le d\)
You need to compute the maximum number of donuts that can be selected while satisfying this condition.
Example:
If n = 5, d = 3 and the freshness ratings are [4, 2, 1, 6, 3]
, the best subset is [1, 2, 3, 4]
because 4 - 1 = 3
, and the answer is 4.
inputFormat
The first line contains two integers n and d where:
- n is the number of donuts.
- d is the maximum allowed difference in freshness ratings.
The second line contains n integers representing the freshness ratings of the donuts.
Input is read from stdin.
outputFormat
Output a single integer which is the maximum number of donuts that can be selected such that the difference between the highest and lowest freshness ratings of the selected donuts is at most d.
Output is written to stdout.
## sample5 3
4 2 1 6 3
4
</p>