Overview

Choose the illumination range \(R\) of a streetlight located at the origin, and maximize the “effect,” which is the total importance of illuminated signs minus the power cost \(R^2\).

Analysis

In this problem, by choosing a non-negative integer \(R\), signs within distance \(R\) from the origin (i.e., \(|X_i| \leq R\)) are illuminated, and the effect is the total importance of those signs minus the cost \(R^2\).

Naive Approach

A naive approach would be to iterate \(R\) from 0 to some upper limit, and for each \(R\), sum up the importance of all signs satisfying \(|X_i| \leq R\), then subtract \(R^2\). However, this method requires checking all signs every time, which could be inefficient.

That said, given the constraints, the maximum absolute value of coordinates is at most 100, so candidates for \(R\) only need to range from 0 to 100. Also, since multiple signs can share the same coordinate, it is efficient to pre-sum the importance values for each coordinate.

Improvement

Performing a full scan for each \(R\) results in a time complexity of about \(O(N \times R_{\text{max}})\), but since the constraints are small, this is fast enough. However, for greater efficiency, we can precompute the total importance at each position and then sum the values within range for each \(R\).

Algorithm

1. Read the coordinate \(X_i\) and importance \(P_i\) of each sign.
2. To sum up the importance of signs at the same coordinate, use a defaultdict to record the total importance at coordinate \(x\) in pos_sum[x].
3. For each possible value of \(R\) (from 0 to the maximum \(|X_i|\)), do the following:
   • Compute the total importance of all signs satisfying \(|X_i| \leq R\).
   • Calculate the effect: \(\left(\sum P_i\right) - R^2\).
   • Update the maximum effect.
4. Output the maximum effect at the end.

Complexity

• Time complexity: \(O(N + R_{\text{max}}^2)\) (where \(R_{\text{max}} = \max |X_i|\), which is at most 100 in this problem)
• Space complexity: \(O(N)\)

※ In practice, since we compute the sum inside the loop over \(R\) each time, the overall complexity is \(O(N \cdot R_{\text{max}})\), but since both \(N\) and \(R_{\text{max}}\) are very small, this is not a problem.

Implementation Notes

• When multiple signs share the same coordinate, their importance values must be summed.

• The case \(R = 0\) must also be considered, so the initial value of the effect should be set to 0.

• It is sufficient to try \(R\) up to the maximum absolute value of the coordinates (increasing \(R\) beyond that has no benefit).

  Source Code

n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

# 座標ごとに重要度を合計するための辞書
import collections
pos_sum = collections.defaultdict(int)
for x, p in data:
    pos_sum[x] += p

# 効果の最大値を計算
max_effect = 0  # R=0 のときは効果が0以上になるので、最低でも0

# 座標の絶対値の最大値まで試せば十分
positions = list(pos_sum.keys())
if not positions:
    print(0)
else:
    max_abs_x = max(abs(x) for x in positions)
    # R を 0 から max_abs_x まで試す
    prefix_sum = 0
    pos_sum_sorted = sorted(pos_sum.items())  # (position, sum of P) のリスト
    j = 0  # pos_sum_sorted のインデックス
    for r in range(max_abs_x + 1):
        # 新しく加わる範囲 [-r, -r+1, ..., r-1, r] に含まれる標識の重要度を加算
        while j < len(pos_sum_sorted) and pos_sum_sorted[j][0] <= r:
            if pos_sum_sorted[j][0] >= -r:
                prefix_sum += pos_sum_sorted[j][1]
            j += 1
        effect = prefix_sum - r * r
        if effect > max_effect:
            max_effect = effect
        # j をリセットせずに次に備えるために、再度調整が必要
    # より正確にするため、prefix_sum を毎回再計算する方式に変更
    max_effect = 0
    for r in range(max_abs_x + 1):
        total = 0
        for x, p_sum in pos_sum.items():
            if abs(x) <= r:
                total += p_sum
        effect = total - r * r
        if effect > max_effect:
            max_effect = effect

    print(max_effect)

---

This editorial was generated by qwen3-coder-480b.