Overview

This problem asks you to choose an illumination range \(R\) (a non-negative integer) for a streetlight placed at the origin, and maximize the “effectiveness,” defined as the sum of importance values of illuminated signs minus the power cost \(R^2\).

Analysis

Key Observations

1. The number of candidates for \(R\) is finite and sufficiently small: Since the coordinates of signs satisfy \(-100 \leq X_i \leq 100\), increasing \(R\) beyond \(100\) does not illuminate any additional signs. Meanwhile, the power cost \(R^2\) keeps increasing, so \(R > 100\) always yields worse effectiveness than \(R = 100\). Therefore, it suffices to check only the \(101\) values \(R = 0, 1, 2, \ldots, 100\).

2. Brute force is fast enough: There are at most \(101\) candidates for \(R\) and at most \(100\) signs, so checking all combinations requires only about \(101 \times 100 = 10{,}100\) computations.

Verification with a Concrete Example

For instance, suppose there is a sign at coordinate \(3\) with importance \(20\), and a sign at coordinate \(-5\) with importance \(50\).

• \(R = 0\): effectiveness \(= 0 - 0 = 0\)
• \(R = 3\): the sign at coordinate \(3\) is illuminated, effectiveness \(= 20 - 9 = 11\)
• \(R = 5\): both signs are illuminated, effectiveness \(= 70 - 25 = 45\)
• \(R = 10\): both signs are illuminated, but effectiveness \(= 70 - 100 = -30\)

As shown, if \(R\) is too large, the cost exceeds the total importance, and the effectiveness decreases.

When R = 0 is Optimal

It is possible that the effectiveness is negative for all \(R \geq 1\). As stated in the problem, when \(R = 0\) the effectiveness is at least \(0\), so the answer is always \(0\) or greater. Setting the initial value to \(0\) ensures correct handling of this case.

Algorithm

1. Read the coordinates and importance values of all signs.
2. Initialize the maximum effectiveness best to \(0\) (since \(R = 0\) guarantees effectiveness of at least \(0\)).
3. For each \(R = 0, 1, 2, \ldots, 100\):
   • Compute the sum of importance values of signs satisfying \(|X_i| \leq R\).
   • Calculate effectiveness \(= (\text{sum of importance values}) - R^2\).
   • Update best if this value is larger.
4. Output best.

Complexity

• Time complexity: \(O(R_{\max} \times N)\) (since \(R_{\max} = 100\), this is \(O(100 \times N)\), which can be considered effectively \(O(N)\))
• Space complexity: \(O(N)\) (for storing the sign information)

Implementation Notes

• Initialize best to \(0\): Since the effectiveness when \(R = 0\) is guaranteed to be at least \(0\), setting the initial value to \(0\) ensures that even if the effectiveness is negative for all \(R\), the correct output of \(0\) is produced.

• Checking abs(x) <= R: The streetlight illuminates symmetrically left and right from the origin, so we determine whether a sign is illuminated by checking if the absolute value of its coordinate is at most \(R\).

• The search range for \(R\) from \(0\) to \(100\) is sufficient: Since the maximum absolute value of coordinates is \(100\), there is no need to try values of \(R\) beyond that.

  Source Code

N = int(input())
signs = []
for _ in range(N):
    x, p = map(int, input().split())
    signs.append((x, p))

best = 0
for R in range(0, 101):
    total = sum(p for x, p in signs if abs(x) <= R)
    effect = total - R * R
    if effect > best:
        best = effect

print(best)

This editorial was generated by claude4.6opus-thinking.