Overview

Choose a non-negative integer illumination radius \(R\) for a streetlight located at the origin, and maximize the “effect,” which is the total importance of illuminated signs \(\sum_{|X_i|\le R}P_i\) minus the cost \(R^2\).

Analysis

• Whether a sign is illuminated is determined by \(|X_i|\le R\), so for each sign we only need to look at its “distance from the origin” \(d_i=|X_i|\) (it doesn’t matter whether it’s to the left or right).
• The effect is $\( \left(\sum_{d_i\le R}P_i\right)-R^2 \)\( As \)R\( increases, the number of illuminated signs tends to grow, but the cost \)R^2$ increases rapidly. The effect is maximized at some point, so we can try all candidates and take the maximum.
• An important observation here is that no matter how large we make \(R\), once \(R>\max_i |X_i|\), no new signs are added (all are already illuminated), yet the cost keeps increasing. Therefore, the optimal \(R\) must exist in the range $\( 0 \le R \le M=\max_i |X_i| \)$
• There is no need to “try infinitely many values of \(R\)”; brute-forcing from \(0\) to \(M\) is sufficient. Given the constraints \(N\le 100\) and \(M\le 100\), checking all signs for each \(R\) is fast enough.

(Example) Suppose signs are at \(X=-2,3\) with importances \(5,10\) respectively, so \(M=3\). - If \(R=2\), the illuminated importance is \(5\), and the effect is \(5-4=1\) - If \(R=3\), the illuminated importance is \(15\), and the effect is \(15-9=6\) As shown, we can exhaustively search over \(R\) and take the maximum.

Algorithm

1. For each input sign, store the distance \(d=|X_i|\) and importance \(P_i\), and compute \(M=\max d\).
2. For \(R=0,1,2,\dots,M\), do the following:
   • Sum the importances of signs satisfying \(d\le R\) to obtain \(s=\sum_{d\le R}P\).
   • Compute the effect \(s-R^2\) and update the maximum value.
3. Output the maximum effect.

Complexity

• Time complexity: \(O(MN)\) (iterate \(R\) from \(0\) to \(M\), checking \(N\) signs each time)
• Space complexity: \(O(N)\) (storing sign information)

Implementation Notes

• Since coordinates are symmetric about the origin, always taking abs(x) and treating it as a distance keeps the code concise.

• The key point is limiting the search range to 0..M (going beyond that only increases cost and is never beneficial).

• By naturally including the \(R=0\) case in the exhaustive search, the condition that the maximum effect is always at least \(0\) is handled automatically.

  Source Code

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()

This editorial was generated by gpt-5.2-high.