Overview

This problem involves maximizing profit by fixing the “fruit with the minimum selling price \(L\)” and the “fruit with the maximum selling price \(R\)” among the chosen fruits, then selecting as many fruits with positive profit as possible between them.

By sorting the fruits in ascending order of selling price and using prefix sums and a sliding window maximum (double-ended queue deque), the problem can be solved efficiently with a time complexity of \(O(N \log N)\).

---

Analysis

1. Sorting by Selling Price and Fixing the Interval

To make the condition that the difference between the maximum and minimum selling prices is at most \(D\) easier to handle, we first sort the fruits in ascending order of selling price \(P_i\).

After sorting, let \(L\) be the fruit with the lowest selling price (smallest index) and \(R\) be the fruit with the highest selling price (largest index) among the chosen fruits. The condition that must be satisfied is: $\(P_R - P_L \le D\)$

2. Optimal Selection When \(L\) and \(R\) Are Fixed

Once we decide to choose \(L\) and \(R\), any fruit \(i\) between them (\(L < i < R\)) does not affect the maximum or minimum selling price when selected (since \(P_L \le P_i \le P_R\) is guaranteed). Therefore, for fruits in between, the optimal strategy is to select all fruits with positive profit \(P_i - C_i\) and skip those with negative profit.

Let the profit of fruit \(i\) be \(V_i = P_i - C_i\). When \(L < R\), the maximum profit obtainable can be expressed as: $\(\text{Profit} = V_L + V_R + \sum_{i=L+1}^{R-1} \max(0, V_i)\)$

※ Note that if only one fruit is selected (\(L=R\)), the profit is simply \(V_R\).

3. Formula Transformation and Use of Prefix Sums

To compute the above formula efficiently, we define the prefix sum of positive profits as \(S_k = \sum_{i=1}^{k} \max(0, V_i)\). Then, the sum of positive profits within the interval can be expressed as \(S_{R-1} - S_L\), so the overall profit formula transforms to:

\[\text{Profit} = V_R + V_L + (S_{R-1} - S_L) = V_R + S_{R-1} + (V_L - S_L)\]

Here, letting \(A_L = V_L - S_L\) denote the part that depends only on \(L\): $\(\text{Profit} = V_R + S_{R-1} + A_L\)$

4. Optimization Using Sliding Window (deque)

Exhaustively searching all pairs of \(L, R\) would take \(O(N^2)\), which exceeds the time limit. Consider iterating \(R\) from \(1\) to \(N\). For each \(R\), the range of \(L\) satisfying \(P_R - P_L \le D\) becomes \(L \in [L_{\min}, R-1]\).

Since selling prices \(P\) are sorted, as \(R\) increases, the left boundary \(L_{\min}\) satisfying the condition also monotonically increases (moves to the right). This forms a “sliding window,” and by using a double-ended queue (deque), we can obtain the maximum value of \(A_L\) within the window in \(O(1)\).

---

Algorithm

1. Preprocessing:

   • Compute the profit \(V_i = P_i - C_i\) for each fruit, then sort the fruits in ascending order of selling price \(P_i\).
   • Compute the prefix sum \(S_i\) of the positive parts of \(V_i\).
   • For each \(i\), compute \(A_i = V_i - S_i\).

2. Sliding Window Maximum Transition: Loop \(R\) from \(1\) to \(N\), performing the following:

   • Adding elements: Add \(R-1\) to the deque. When doing so, remove all elements from the back of the deque whose value \(A\) is less than or equal to \(A_{R-1}\) (this ensures the deque always maintains descending order).
   • Removing out-of-range elements: For the element \(L\) at the front of the deque, remove it from the front as long as \(P_R - P_L > D\) (since it no longer satisfies the condition).
   • Updating the maximum:
     • If the deque is not empty, the element at the front is the optimal \(L\). Compute the profit \(V_R + S_{R-1} + A_L\) and consider it as a candidate for the answer.
     • The profit \(V_R\) from selecting only fruit \(R\) alone is also a candidate.
     • Update the overall maximum among these candidates.

---

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the fruits takes \(O(N \log N)\).
  • In the subsequent traversal of \(R\), each element is added to the deque at most once and removed at most once, so the sliding window maximum part is \(O(N)\) overall. Therefore, sorting is the bottleneck.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the sorted array, prefix sums, deque, etc.

---

Implementation Notes

• Careful with initial values: Since it is possible that all fruits have negative profit, the variable ans holding the maximum profit must be initialized to a sufficiently small value (e.g., \(-10^{18}\)).

• Handling 1-indexed arrays: When working with the prefix sum \(S\) and array \(A\), implementing with \(1\)-indexed arrays prevents off-by-one errors, making the code simpler and reducing bugs.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    D = int(input_data[1])

    C = [int(x) for x in input_data[2::2]]
    P = [int(x) for x in input_data[3::2]]

    items = sorted(zip(P, [p - c for p, c in zip(P, C)]))

    items_p = [0] * (N + 1)
    items_v = [0] * (N + 1)
    for i in range(N):
        items_p[i + 1] = items[i][0]
        items_v[i + 1] = items[i][1]

    S = [0] * (N + 1)
    A = [0] * (N + 1)

    for i in range(1, N + 1):
        v = items_v[i]
        S[i] = S[i - 1] + (v if v > 0 else 0)
        A[i] = v - S[i]

    from collections import deque

    deq = deque()
    ans = -9000000000000000000

    for R in range(1, N + 1):
        v_R = items_v[R]
        p_R = items_p[R]

        if R - 1 >= 1:
            val = A[R - 1]
            while deq and A[deq[-1]] <= val:
                deq.pop()
            deq.append(R - 1)

        while deq and p_R - items_p[deq[0]] > D:
            deq.popleft()

        current_max = v_R
        if deq:
            opt_L = deq[0]
            cand = v_R + S[R - 1] + A[opt_L]
            if cand > current_max:
                current_max = cand
        if current_max > ans:
            ans = current_max

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.