Overview

Select fruits such that the difference between the maximum and minimum selling prices \(P_i\) is at most \(D\), and maximize the profit \(\sum(P_i-C_i)\). By sorting by \(P_i\) and considering a “sliding window of valid selling price intervals,” we can solve this efficiently.

Analysis

Key Observations

• The condition “the difference between the maximum and minimum selling prices of selected fruits \(\le D\)” depends only on the range of selling prices \(P\).
• If we sort the fruits in ascending order of selling price \(P\), a valid set corresponds to selecting elements contained within some interval \([l, r]\) (a contiguous portion).
  (Mixing in elements outside the interval would widen the min/max and violate the condition)

Optimal Selection Within a Fixed Interval

Within a given interval (window), the selling price condition is already satisfied. Therefore, we only need to think about maximizing profit: - Fruits with positive profit are beneficial to select - Fruits with negative profit are better left unselected
Thus, the optimal profit for that window is “the sum of only the positive profits.”

Handling the “Must Select at Least One” Constraint

With the above approach, if there are no positive-profit fruits within a window, the total becomes \(0\), which violates “select at least one” (it’s effectively the same as selecting nothing). - If there exists a window that can produce a positive total profit, then its maximum is the answer - Otherwise (the positive profit sum is \(0\) for every window), since we must select at least one, we optimally select the single fruit with the maximum profit (the least loss / most gain)
In other words, the answer is: - \(\max(\text{maximum positive profit sum across all windows},\ \max_i(P_i-C_i))\)

Why the Naive Solution is Too Slow

If we try all intervals satisfying the min/max selling price condition, there are \(O(N^2)\) intervals. Computing the positive profit sum for each interval adds further cost, making it infeasible for \(N \le 2\times 10^5\).

Algorithm

1. For each fruit, compute the profit \(v_i = P_i - C_i\) and create pairs \((P_i, v_i)\).
2. Sort in ascending order by selling price \(P\).
3. Use the two-pointer (sliding window) technique, extending the right end \(r\) from \(0\) onward:
   • Maintain sum_pos, the sum of “positive profits” within the current window \([l, r]\)
     
     • If \(v_r>0\), then sum_pos += v_r
   • While the window violates the condition (\(P_r - P_l > D\)), advance the left end \(l\) to shrink it
     
     • If the removed element has \(v_l>0\), then sum_pos -= v_l
4. For each \(r\), update the maximum best_sum_pos with sum_pos.
5. Simultaneously, compute the overall single-element maximum profit max_profit = max_i v_i.
6. Finally:
   • If best_sum_pos > 0, that is the answer (a window containing positive profit exists)
   • Otherwise, max_profit is the answer (since we must select at least one)

Complexity

• Time complexity: \(O(N\log N)\) for sorting, and \(O(N)\) for the two-pointer part since each element moves at most once through the left and right pointers, giving a total of \(O(N\log N)\)
• Space complexity: \(O(N)\) for the sorting array, etc.

Implementation Notes

• Each time an element is added to or removed from the window, add or subtract only “positive profits” (ignore negatives).

• If best_sum_pos remains \(0\), it likely means “there is no selection that yields positive profit,” so fall back to single-element maximum profit max_profit.

• The total profit can be on the order of \(N \times 10^9\), so depending on the language, 64-bit integers may be required (Python handles this automatically with arbitrary precision, so it’s not an issue).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n, d = data[0], data[1]
    items = []
    max_profit = -10**30

    idx = 2
    for _ in range(n):
        c = data[idx]
        p = data[idx + 1]
        idx += 2
        prof = p - c
        items.append((p, prof))
        if prof > max_profit:
            max_profit = prof

    items.sort()  # sort by selling price P

    l = 0
    sum_pos = 0
    best_sum_pos = 0

    for r in range(n):
        pr, vr = items[r]
        if vr > 0:
            sum_pos += vr
        while pr - items[l][0] > d:
            vl = items[l][1]
            if vl > 0:
                sum_pos -= vl
            l += 1
        if sum_pos > best_sum_pos:
            best_sum_pos = sum_pos

    if best_sum_pos > 0:
        print(best_sum_pos)
    else:
        print(max_profit)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.