概要

売値 \(P_i\) の最大値と最小値の差が \(D\) 以下になるように果物を選び、利益 \(\sum(P_i-C_i)\) を最大化します。\(P_i\) でソートして「条件を満たす売値区間（スライドする窓）」を考えることで高速に解けます。

考察

重要な気づき

• 条件「選んだ果物の売値の最大値と最小値の差 \(\le D\)」は、売値 \(P\) の範囲だけで決まります。
• 果物を売値 \(P\) で昇順に並べると、条件を満たす集合は「ある区間 \([l, r]\)（連続部分）」に含まれる要素から選ぶことに対応します。
  （区間外の要素を混ぜると最小・最大が広がって条件違反になるため）

区間が決まったときの最適な選び方

ある区間（窓）内では、売値の条件はすでに満たされています。よって利益最大化だけ考えればよく、 - 利益が正の果物は選ぶと得 - 利益が負の果物は選ばない方が得
となるため、その窓での最適利益は「正の利益だけの合計」です。

「必ず1個選ぶ」制約への対応

上の方針だと、窓内に正の利益が1つもない場合、合計が \(0\) になってしまい「1個以上選ぶ」に反します（実際は何も選んでいないのと同じ）。 - もし全体として正の利益を作れる窓があるなら、その最大値が答え - そうでない（どの窓でも正の利益合計が \(0\)）なら、1個は選ぶ必要があるので、利益が最大の1個（最も損が少ない／最も得な）を選ぶのが最適
つまり答えは
- \(\max(\text{どこかの窓の正利益合計の最大},\ \max_i(P_i-C_i))\)
になります。

素朴解がなぜ遅いか

売値の最小・最大を満たす区間をすべて試すと、区間は \(O(N^2)\) 個あります。各区間で正利益合計を数えるとさらにかかり、\(N \le 2\times 10^5\) では間に合いません。

アルゴリズム

1. 各果物について利益 \(v_i = P_i - C_i\) を計算し、ペア \((P_i, v_i)\) を作る。
2. 売値 \(P\) で昇順ソートする。
3. しゃくとり法（2ポインタ）で、右端 \(r\) を \(0\) から順に伸ばす：
   • 現在の窓 \([l, r]\) に含まれる「正の利益」の合計 sum_pos を管理する
     
     • \(v_r>0\) なら sum_pos += v_r
   • 窓が条件違反（\(P_r - P_l > D\)）の間、左端 \(l\) を進めて縮める
     
     • 取り除く要素 \(v_l>0\) なら sum_pos -= v_l
4. 各 \(r\) で sum_pos の最大値 best_sum_pos を更新する。
5. 同時に、全体の単体最大利益 max_profit = max_i v_i も求めておく。
6. 最終的に
   • best_sum_pos > 0 ならそれが答え（正利益を含む窓がある）
   • そうでなければ max_profit が答え（必ず1個選ぶため）

計算量

• 時間計算量: ソートに \(O(N\log N)\)、しゃくとり部分は各要素が高々1回ずつ左右ポインタで動くので \(O(N)\)、合計で \(O(N\log N)\)
• 空間計算量: ソート用配列などで \(O(N)\)

実装のポイント

• 窓から要素を追加・削除するたびに、「正の利益だけ」を加減算する（負は無視）。

• best_sum_pos が \(0\) のままなら「正の利益を得られる選び方が存在しない」可能性が高いので、単体最大利益 max_profit にフォールバックする。

• 利益合計は最大で \(N \times 10^9\) 規模になり得るため、言語によっては 64bit 整数が必要（Python は自動で多倍長なので問題なし）。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。