概要

各商品を「売るか売らないか」独立に選べるので、利益がプラスになる商品だけを選んだときの合計利益（最大値）を求める問題です。

考察

商品集合 \(S\) を選んだときの利益は $\(\sum_{i \in S} A_i - \sum_{i \in S} B_i = \sum_{i \in S} (A_i - B_i)\)\( と変形できます。つまり、各商品 \)i\( の「純利益」\)d_i = A_i - B_i$ を足し合わせる問題になります。

ここで重要な観察は次の通りです。

• ある商品 \(i\) の \(d_i\) が 正 なら、その商品を選ぶと利益が \(d_i\) だけ増える。
• \(d_i\) が 0 以下 なら、その商品を選ぶと利益は増えない（同じか減る）。

商品ごとに選択が独立なので、「他の商品との組み合わせで得になる」といった相互作用はありません。したがって、

• \(d_i > 0\) の商品は 必ず売る
• \(d_i \le 0\) の商品は 売らない

のが最適です。

素朴に「全ての部分集合を試す」方法だと、組み合わせは \(2^N\) 通りあり、\(N \le 2 \times 10^5\) では到底間に合いません（TLE）。
上の観察により、各商品を1回見るだけで最適解が決まります。

例： - \((A,B)=(100,70)\) なら \(d=30\) → 売る - \((A,B)=(50,80)\) なら \(d=-30\) → 売らない
合計は正の \(d\) だけ足せばよいです。

アルゴリズム

1. 答え ans = 0 を用意する。
2. 各商品について \(d = A_i - B_i\) を計算する。
3. もし \(d > 0\) なら ans += d する（利益が増える分だけ足す）。
4. 最後に ans を出力する。

「選ばない」ことも可能なので、負の値を足してしまう必要はなく、結果として最大利益は自然に \(0\) 以上になります。

計算量

• 時間計算量: \(O(N)\)（各商品を1回ずつ処理）
• 空間計算量: \(O(1)\)（追加で大きな配列を持たない）

実装のポイント

• \(A_i, B_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、合計は最大で \(2 \times 10^{14}\) 程度になり得ます。Python の int は大丈夫ですが、他言語では 64bit 整数が必要です。

• 入力が大きいので、Python では sys.stdin.buffer.readline を使うと安全に高速化できます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    ans = 0
    for _ in range(N):
        a, b = map(int, input().split())
        d = a - b
        if d > 0:
            ans += d
    print(ans)

if __name__ == "__main__":
    main()

---

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