Overview

This problem asks us to maximize the total profit (selling price \(-\) purchase price) of selected fruits, under the constraint that the difference between the maximum and minimum selling prices of the selected fruits is at most \(D\).

By sorting by selling price, we can efficiently compute the optimal solution in \(O(N \log N)\) using prefix sums and a sliding window (monotonic queue), when we fix the “minimum selling price” and “maximum selling price” of the selected fruits.

---

Analysis

1. Sorting by Selling Price and Determining the Interval

To make the condition “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 smallest selling price (smallest index) and \(R\) be the fruit with the largest selling price (largest index) among the selected fruits (\(L \le R\)). To satisfy the condition, we need \(P_R - P_L \le D\).

2. Choosing Fruits in Between

When \(L\) and \(R\) are selected, any fruit \(i\) between them (\(L < i < R\)) does not affect the “difference between the maximum and minimum values” whether it is selected or not (because after sorting, \(P_L \le P_i \le P_R\) is guaranteed). Therefore, to maximize profit, it is optimal to select all fruits between them whose profit \(V_i = P_i - C_i\) is positive.

Thus, we consider two cases: selecting exactly 1 fruit (\(L = R\)) and selecting 2 or more fruits (\(L < R\)).

• Selecting exactly 1 fruit (\(L = R\)): The profit is \(V_L\).
• Selecting 2 or more fruits (\(L < R\)): The profit can be expressed as: $\( \text{profit} = V_L + V_R + \sum_{i=L+1}^{R-1} \max(0, V_i) \)$

3. Speeding Up Through Formula Transformation

We transform the profit formula for the case of selecting 2 or more fruits into a form that can be computed efficiently. Define the prefix sum of positive profits as \(S_k = \sum_{i=1}^k \max(0, V_i)\) (with \(S_0 = 0\)). Using this, the intermediate sum can be expressed as \(S_{R-1} - S_L\).

\[ \begin{aligned} \text{profit} &= V_L + V_R + S_{R-1} - S_L \\ &= (V_L - S_L) + (V_R + S_{R-1}) \end{aligned} \]

Here, we use the identity \(\max(0, V_x) = V_x - \min(0, V_x)\) to simplify further. - \(V_L - S_L = V_L - (S_{L-1} + \max(0, V_L)) = \min(0, V_L) - S_{L-1}\) - \(V_R + S_{R-1} = V_R + (S_R - \max(0, V_R)) = \min(0, V_R) + S_R\)

Substituting these, the profit formula can be completely separated into terms for \(L\) and terms for \(R\): $\( \text{profit} = \left( \min(0, V_L) - S_{L-1} \right) + \min(0, V_R) + S_R \)$

Defining \(A_i = \min(0, V_i) - S_{i-1}\), the profit simplifies to: $\( \text{profit} = A_L + \min(0, V_R) + S_R \)$

4. Applying the Sliding Window

When \(R\) is fixed, the conditions to satisfy are: - \(1 \le L < R\) - \(P_R - P_L \le D\)

By maximizing \(A_L\) within the range satisfying these conditions, we obtain the maximum profit for that \(R\). As \(R\) moves to the right, the lower bound of \(L\) satisfying the condition (\(L_{\min}\)) also moves to the right. This is a classic sliding window maximum problem, and by using a double-ended queue (std::deque), we can find the optimal \(L\) for all \(R\) in linear time.

---

Algorithm

1. Preprocessing:
   • Sort the fruits in ascending order of selling price \(P_i\).
   • Compute the profit \(V_i = P_i - C_i\) for each fruit.
   • Compute the prefix sum of positive profits \(S_i\).
   • Compute \(A_i = \min(0, V_i) - S_{i-1}\) for each \(i\).
2. Initialization:
   • Set the initial answer to the maximum value when selecting exactly 1 fruit (\(\max_{1 \le i \le N} V_i\)).
3. Sliding Window:
   • Loop \(R\) from \(2\) to \(N\).
   • Add the newly available \(L = R-1\) to the deque. To maintain monotonicity, remove elements from the back of the deque that are less than or equal to \(A_{R-1}\).
   • While \(P_R - P_{L_{\min}} > D\), advance \(L_{\min}\) to the right.
   • If the index at the front of the deque is less than \(L_{\min}\), remove it as it is outside the window.
   • Let \(L\) be the index at the front of the deque, and update the answer with the profit \(A_L + \min(0, V_R) + S_R\).

---

Complexity

• Time Complexity: \(O(N \log N)\)

  • Sorting the fruits takes \(O(N \log N)\).
  • In the sliding window transitions, each index is added to and removed from the deque at most once, so this part is \(O(N)\).
  • Therefore, the overall bottleneck is the sorting, giving a total of \(O(N \log N)\).

• Space Complexity: \(O(N)\)

  • Storing the fruit information, prefix sums, and the deque uses \(O(N)\) memory.

---

Implementation Notes

• Handling the case of selecting exactly 1 fruit: In cases such as when all fruits have negative profit, selecting just 1 fruit may yield higher profit than selecting multiple. Therefore, the initial answer must always be initialized with the “maximum value when selecting exactly 1 fruit”.

• Attention to data types: The total profit and prefix sums can become very large values (or very small negative values), so in C++ use the long long type, and set the initial “negative infinity” to a sufficiently small value (such as -4e18).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

struct Fruit {
    long long C, P, V;
    bool operator<(const Fruit& other) const {
        return P < other.P;
    }
};

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<Fruit> fruits(N);
    for (int i = 0; i < N; ++i) {
        cin >> fruits[i].C >> fruits[i].P;
        fruits[i].V = fruits[i].P - fruits[i].C;
    }

    // Sort fruits by selling price P
    sort(fruits.begin(), fruits.end());

    vector<long long> V(N + 1), P(N + 1);
    for (int i = 1; i <= N; ++i) {
        V[i] = fruits[i - 1].V;
        P[i] = fruits[i - 1].P;
    }

    vector<long long> V_plus(N + 1);
    for (int i = 1; i <= N; ++i) {
        V_plus[i] = max(0LL, V[i]);
    }

    // Prefix sums of positive profits
    vector<long long> S(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        S[i] = S[i - 1] + V_plus[i];
    }

    // Auxiliary array for RMQ
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        A[i] = min(0LL, V[i]) - S[i - 1];
    }

    // Base case: choosing exactly 1 fruit
    long long ans = -4e18; // Negative infinity
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, V[i]);
    }

    // Sliding window maximum using deque
    deque<int> dq;
    int L_min = 1;
    for (int R = 2; R <= N; ++R) {
        int new_L = R - 1;
        while (!dq.empty() && A[dq.back()] <= A[new_L]) {
            dq.pop_back();
        }
        dq.push_back(new_L);

        // Maintain the condition P[R] - P[L_min] <= D
        while (P[R] - P[L_min] > D) {
            L_min++;
        }

        // Remove elements out of the current window [L_min, R-1]
        while (!dq.empty() && dq.front() < L_min) {
            dq.pop_front();
        }

        if (!dq.empty()) {
            long long max_A = A[dq.front()];
            long long current_val = max_A + min(0LL, V[R]) + S[R];
            ans = max(ans, current_val);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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