概要

各パイプの「有効長」を先に計算し、どの本数 \(M\) を選ぶのが最も得かを調べる問題です。
本質は「有効長の大きい順に選ぶのが最適」であり、ソート＋累積和で最大値を高速に求められます。

考察

完成長は、選んだ本数を \(M\)、その有効長の合計を \(S\) とすると \( S - (M-1)K \) です。

1. まず有効長に変換する

• 錆びていない: \(A_i\)
• 錆びている: \(\max(A_i - C, 0)\)

これで「各パイプの価値」は有効長 \(v_i\) として統一できます。

---

2. どのパイプ集合を選ぶべきか？

本数を \(M\) に固定すると、引かれる接続コスト \((M-1)K\) は定数です。
つまりこのとき最大化すべきは 有効長の合計 \(S\) だけです。

したがって、本数 \(M\) 固定なら
有効長が大きいものを上から \(M\) 本選ぶ のが最適です（交換 argument）。

---

3. 全探索の何がまずいか

パイプの部分集合を全部試すと \(2^N\) 通りで不可能です（\(N \le 10^5\)）。
しかし上の性質により、「本数 \(M=1..N\) ごとに上位 \(M\) 本を見る」だけで十分になります。

---

4. どう高速化するか

有効長を降順ソートして \( v_1 \ge v_2 \ge \cdots \ge v_N \) とします。
このとき \(M=i\) 本選ぶ最良値は \( (v_1+\cdots+v_i) - (i-1)K \) です。
左側の和は累積和で順に更新できるので、1回の走査で全 \(i\) を評価できます。

具体的にはコード中の - s: 先頭からの有効長合計 - total = s - (i - 1) * K - best = max(best, total)

で実現しています。

最後に best >= D なら best、そうでなければ -1 を出力します。

アルゴリズム

1. 入力を受け取り、各パイプの有効長 \(v_i\) を計算する。
   
   • 錆びありなら \(\max(A_i-C,0)\)
   • 錆びなしなら \(A_i\)
2. 有効長配列を降順ソートする。
3. 先頭から 1 本ずつ追加しながら累積和 s を更新し、各本数 \(i\) で \( \text{total} = s - (i-1)K \) を計算して最大値 best を更新する。
4. best >= D なら best を出力、そうでなければ -1 を出力。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（有効長配列）

実装のポイント

• 錆びたときの有効長は負にならないように max(A-C, 0) を忘れない。

• 値は最大で大きくなるため（合計は最大 \(10^{14}\) 規模）、整数型オーバーフローに注意（Python は自動で安全）。

• best は 0 から始めて問題ありません（有効長がすべて 0 の場合でも正しく処理できる）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D, K, C = map(int, input().split())

    vals = []
    for _ in range(N):
        A, B = map(int, input().split())
        if B == 1:
            v = A - C
            if v < 0:
                v = 0
        else:
            v = A
        vals.append(v)

    vals.sort(reverse=True)

    best = 0
    s = 0
    for i, v in enumerate(vals, 1):  # i = number of selected pipes
        s += v
        total = s - (i - 1) * K
        if total > best:
            best = total

    if best >= D:
        print(best)
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

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