Official Analysis (Java)

Solution

Explanation

We first sort the diamonds by size, which allows us to consider groups of diamonds in order. For each diamond, we determine the maximum number of diamonds that can be grouped with it without exceeding the allowed size difference.

We precompute the best grouping possible from every starting point so that once we fix a group for one case, we can quickly identify the optimal group for the second case from the remaining larger diamonds.

Finally, we combine the two groups to determine the maximum total number of diamonds that can be showcased across both cases.

Implementation

Time Complexity: $\mathcal{O} (N \log{N})$

Copy
import sys

sys.stdin = open("diamond.in", "r")
sys.stdout = open("diamond.out", "w")

n, k = map(int, input().split())
arr = sorted([int(input()) for i in range(n)])

# maximum number of diamonds assuming i is the smallest diamond
max_diamond = [0] * (n + 1)