概要

原点にある街灯の照明半径 \(R\)（非負整数）を選び、照らされる標識の重要度合計 \(\sum_{|X_i|\le R}P_i\) からコスト \(R^2\) を引いた「効果」を最大化します。

考察

• 照らされるかどうかは \(|X_i|\le R\) で決まるので、各標識は「原点からの距離」\(d_i=|X_i|\) のみを見れば十分です（左右どちらにあるかは無関係）。
• 効果は $\( \left(\sum_{d_i\le R}P_i\right)-R^2 \)\( で、\)R\( を大きくすると「照らせる標識」は増えやすい一方、「コスト \)R^2$」が急激に増えます。どこかで最大になるため、全候補を試して最大値を取ればよいです。
• ここで重要な観察として、\(R\) をどれだけ大きくしても、\(R>\max_i |X_i|\) の範囲では新しい標識は増えません（全て照らし尽くしている）にもかかわらずコストだけが増えます。したがって最適な \(R\) は $\( 0 \le R \le M=\max_i |X_i| \)$ の範囲に必ず存在します。
• 素朴に「\(R\) を無限に試す」必要はなく、\(0\) から \(M\) まで総当たりすれば十分です。制約は \(N\le 100\)、\(M\le 100\) なので、\(R\) ごとに全標識を確認しても間に合います。

（例）標識が \(X=-2,3\) にあり、重要度がそれぞれ \(5,10\) のとき、\(M=3\)。
- \(R=2\) なら照らされる重要度は \(5\)、効果は \(5-4=1\)
- \(R=3\) なら照らされる重要度は \(15\)、効果は \(15-9=6\)
このように \(R\) を全探索して最大を取ればよいと分かります。

アルゴリズム

1. 入力された各標識について距離 \(d=|X_i|\) と重要度 \(P_i\) を保存し、\(M=\max d\) を求める。
2. \(R=0,1,2,\dots,M\) について以下を行う。
   • \(d\le R\) を満たす標識の重要度を合計して \(s=\sum_{d\le R}P\) を得る。
   • 効果 \(s-R^2\) を計算し、最大値を更新する。
3. 最大の効果を出力する。

計算量

• 時間計算量: \(O(MN)\)（\(R\) を \(0..M\) で回し、各回で \(N\) 個を見る）
• 空間計算量: \(O(N)\)（標識情報を保持）

実装のポイント

• 座標は左右対称なので必ず abs(x) を取って距離として扱うと簡潔になります。

• 探索範囲を 0..M に限定するのがポイントです（それ以上はコスト増で不利）。

• \(R=0\) のケースも自然に含めて全探索すると、効果の最大値が必ず \(0\) 以上になる条件もそのまま扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    signs = []
    M = 0
    for _ in range(N):
        x, p = map(int, input().split())
        signs.append((abs(x), p))
        if abs(x) > M:
            M = abs(x)

    ans = 0
    for R in range(M + 1):
        s = 0
        for d, p in signs:
            if d <= R:
                s += p
        ans = max(ans, s - R * R)

    print(ans)

if __name__ == "__main__":
    main()

---

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