概要

この問題は、選んだ果物の中で「売値が最小の果物 \(L\)」と「売値が最大の果物 \(R\)」を固定したときに、その間にある利益がプラスの果物をできるだけ多く選ぶことで、利益を最大化する問題です。

果物を売値の昇順にソートし、累積和とスライド最大値（両端キュー deque）を用いることで、時間計算量 \(O(N \log N)\) で効率的に解くことができます。

---

考察

1. 売値によるソートと区間の固定

売値の最大値と最小値の差が \(D\) 以下という条件を扱いやすくするため、まずは果物を売値 \(P_i\) の昇順にソートします。

ソート後、選んだ果物のうち、最も売値が安い（インデックスが最小の）果物を \(L\)、最も売値が高い（インデックスが最大の）果物を \(R\) とします。このとき、満たすべき条件は以下のようになります。 $\(P_R - P_L \le D\)$

2. \(L\) と \(R\) を固定したときの最適な選び方

\(L\) と \(R\) を選ぶと決めたとき、その間にある任意の果物 \(i\) （\(L < i < R\)）は、選んでも売値の最大値・最小値に影響を与えません（\(P_L \le P_i \le P_R\) が保証されるため）。 したがって、間にある果物については、利益 \(P_i - C_i\) がプラスのものはすべて選び、マイナスのものは選ばない のが最適です。

果物 \(i\) の利益を \(V_i = P_i - C_i\) とします。 \(L < R\) のときに得られる最大利益は、次のように表せます。 $\(\text{利益} = V_L + V_R + \sum_{i=L+1}^{R-1} \max(0, V_i)\)$

※なお、果物を \(1\) 個だけ選ぶ（\(L=R\)）場合の利益は単に \(V_R\) となります。

3. 式の変形と累積和の利用

上記の式を高速に計算するために、正の利益の累積和 \(S_k = \sum_{i=1}^{k} \max(0, V_i)\) を定義します。 すると、区間内の正の利益の総和は \(S_{R-1} - S_L\) と表せるため、全体の利益の式は以下のように変形できます。

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

ここで、\(L\) のみに依存する部分を \(A_L = V_L - S_L\) とおくと、 $\(\text{利益} = V_R + S_{R-1} + A_L\)$ となります。

4. スライディングウィンドウ（deque）による高速化

すべての \(L, R\) のペアを全探索すると \(O(N^2)\) かかり、実行時間制限に間に合いません。 \(R\) を \(1\) から \(N\) まで順に動かしていくことを考えます。このとき、条件 \(P_R - P_L \le D\) を満たす \(L\) の範囲は \(L \in [L_{\min}, R-1]\) のようになります。

売値 \(P\) はソートされているため、 \(R\) が増加するにつれて、条件を満たす左端 \(L_{\min}\) も単調に増加（右に移動）します。 これは「スライディングウィンドウ」の形をしており、両端キュー（deque） を用いることで、ウィンドウ内における \(A_L\) の最大値を \(O(1)\) で取得できるようになります。

---

アルゴリズム

1. 前処理:

   • 各果物を \(V_i = P_i - C_i\)（利益）が計算された状態で、売値 \(P_i\) の昇順にソートします。
   • \(V_i\) の正の部分の累積和 \(S_i\) を計算します。
   • 各 \(i\) に対して、 \(A_i = V_i - S_i\) を計算します。

2. スライド最大値の遷移: \(R\) を \(1\) から \(N\) までループしながら、以下を行います。

   • 要素の追加: \(R-1\) を deque に追加します。この際、deque の末尾にある要素のうち、値 \(A\) が \(A_{R-1}\) 以下のものをすべて取り除きます（これにより deque 内が常に降順に保たれます）。
   • 範囲外の削除: deque の先頭の要素 \(L\) について、\(P_R - P_L > D\) である限り、条件を満たさなくなったため deque の先頭から削除します。
   • 最大値の更新:
     • deque が空でなければ、先頭にある要素が最適な \(L\) となります。このときの利益 \(V_R + S_{R-1} + A_L\) を計算し、答えの候補とします。
     • 果物を \(R\) の \(1\) 個だけ選ぶ場合の利益 \(V_R\) も候補とします。
     • これらの中から全体の最大値を更新していきます。

---

計算量

• 時間計算量: \(O(N \log N)\)
  • 果物のソートに \(O(N \log N)\) かかります。
  • その後の \(R\) の走査において、各要素は deque に高々1回追加され、高々1回削除されるため、スライド最大値の部分は全体で \(O(N)\) です。したがって、ソートがボトルネックとなります。
• 空間計算量: \(O(N)\)
  • ソート後の配列や、累積和、deque などの保持に \(O(N)\) のメモリを使用します。

---

実装のポイント

• 初期値の注意: すべての果物の利益が負になる場合もあるため、最大利益を保持する変数 ans の初期値は十分に小さな値（例えば \(-10^{18}\) など）に設定する必要があります。

• 1-indexed の取り扱い: 累積和 \(S\) や配列 \(A\) を扱う際、インデックスのズレを防ぐために \(1\)-indexed で実装すると、コードがシンプルになりバグを減らすことができます。

  ソースコード

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()

---

この解説は gemini-3.5-flash-thinking によって生成されました。