Overview

Given \(N\) fruits, select one or more such that the difference between the maximum and minimum selling prices is at most \(D\), and maximize the total profit (selling price − purchase price). We solve this efficiently by sorting by selling price and using the two-pointer technique (sliding window).

Analysis

Key Observations

Observation 1: Sorting by selling price makes the constraint easier to handle

The condition that the difference between the maximum and minimum selling prices is at most \(D\) can be transformed as follows: if we sort the fruits in ascending order of selling price \(P_i\), then it becomes “for a contiguous interval \([l, r]\), \(P[r] - P[l] \leq D\)”. This is because the selling prices of the chosen fruits must always fall within such an interval.

Observation 2: Optimal selection within a valid window

When a valid interval (one satisfying \(P[r] - P[l] \leq D\)) is determined, which fruits should we select from it?

• Fruits with positive profit: Selecting them increases the total profit, so we should select all of them
• Fruits with non-positive profit: Selecting them decreases (or doesn’t change) the total profit, so it’s better not to select them
• However, if there are no fruits with positive profit in the interval, we are obligated to select at least one, so we select only the one with the largest profit (smallest loss)

Problem with the Naive Approach

Trying all subsets takes \(O(2^N)\), which is far too slow. Examining each fruit for all intervals \([l, r]\) results in \(O(N^2)\), which is too slow for \(N = 2 \times 10^5\).

Solution

Using the two-pointer technique, we can enumerate valid intervals in \(O(N)\) while efficiently maintaining the “sum of positive profits” and “maximum profit” for each interval.

Algorithm

1. For each fruit, create a pair \((P_i, P_i - C_i)\) (selling price and profit), and sort in ascending order of selling price.
2. Move the right end \(r\) from \(0\) to \(N-1\), advancing the left end \(l\) as long as \(P[r] - P[l] > D\) (two-pointer technique).
3. Maintain the following within the window:
   • sum_positive: sum of profits of fruits with positive profit
   • count_positive: number of fruits with positive profit
   • SortedList: manages all profits in the window (retrieves maximum in \(O(\log N)\))
4. Compute the candidate value for each window:
   • If count_positive > 0, the candidate is sum_positive (take all positive profits)
   • Otherwise, the candidate is the maximum value in SortedList (choose the least bad one)
5. The maximum candidate value across all windows is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, and each element’s addition/removal in SortedList is \(O(\log N)\) during the two-pointer sweep)
• Space complexity: \(O(N)\) (for the fruit array and SortedList)

Implementation Notes

• Using SortedList: Since Python’s standard library does not have a balanced binary search tree, we use SortedList from the sortedcontainers library to efficiently retrieve the maximum profit within the window. sl[-1] accesses the maximum value in \(O(\log N)\).

• Correctness of the two-pointer technique: Since fruits are sorted by selling price, all fruits in window \([l, r]\) have selling price differences of at most \(D\). With the right end fixed, we move the left end as far left as possible to maximize the window and increase the number of selectable candidates.

• Cases where the answer is negative: Even when all fruits have negative profit, we must select at least one, so we initialize the answer to -inf to correctly capture the maximum profit (the one with the smallest loss).

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        fruits.append((P, P - C))
    
    # Sort by P (selling price)
    fruits.sort(key=lambda x: x[0])
    
    # Sliding window: for each window [l, r] where fruits[r].P - fruits[l].P <= D,
    # we want to maximize the sum of positive profits + (if all profits are negative, 
    # we must pick the maximum single profit).
    #
    # Strategy: Use a sliding window on sorted P values.
    # For each right endpoint r, find the smallest l such that P[r] - P[l] <= D.
    # Within this window, we want to pick all fruits with positive profit (P_i - C_i > 0)
    # and sum them up. If no fruit has positive profit, pick the one with maximum profit.
    #
    # We need to efficiently track:
    # 1. Sum of positive profits in the window
    # 2. Count of positive profits in the window
    # 3. Maximum profit in the window (for the case all are negative)
    #
    # Actually, the answer for a window is:
    # - If there are positive profit items: sum of positive profits
    # - Else: max profit (which is negative or zero)
    #
    # But we also need to consider: even if there are positive profit items, 
    # we must select at least 1, which is already satisfied by selecting positive ones.
    #
    # We want the maximum over all valid windows.
    
    # We can use a sliding window approach with a multiset to track max profit
    # and maintain sum of positive profits.
    
    ans = -float('inf')
    l = 0
    sum_positive = 0
    count_positive = 0
    # Use a SortedList to get maximum profit in window efficiently
    sl = SortedList()
    
    for r in range(N):
        p, profit = fruits[r]
        if profit > 0:
            sum_positive += profit
            count_positive += 1
        sl.add(profit)
        
        # Shrink window from left if price difference exceeds D
        while fruits[r][0] - fruits[l][0] > D:
            p_l, profit_l = fruits[l]
            if profit_l > 0:
                sum_positive -= profit_l
                count_positive -= 1
            sl.remove(profit_l)
            l += 1
        
        # Calculate best for this window
        if count_positive > 0:
            candidate = sum_positive
        else:
            # All profits <= 0, must pick the maximum one
            candidate = sl[-1]
        
        if candidate > ans:
            ans = candidate
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.