Overview

Choose a non-negative integer R for the range illuminated by a streetlight, and maximize the “effect,” which is the total importance of illuminated signs minus the power cost R².

Analysis

The formula for calculating the effect is \(\left(\sum_{|X_i| \leq R} P_i\right) - R^2\). Since the number of signs N is at most 100, which is small, we can consider trying all possible values of R. However, since R can theoretically take infinitely many values, a complete search is impossible.

A key observation is that the effect only changes around the absolute values of the sign coordinates. This is because the moment R exceeds the absolute value of a sign’s coordinate, that sign becomes illuminated, and the effect increases. Therefore, the candidate values for R can be limited to the absolute values of the sign coordinates, those values plus 1, and R=0.

Algorithm

1. Initialize the set of candidate R values (always include R=0)
2. For each sign, add its coordinate’s absolute value and absolute value + 1 to the candidates
3. For each candidate R, calculate the effect
   • Check all signs, and if |X_i| ≤ R, add the importance
   • Subtract R² from the total importance to compute the effect
4. Find the maximum among the calculated effects

Complexity

• Time complexity: \(O(N^2)\)
  • The number of candidates is at most \(2N+1\) (approximately 200)
  • For each candidate, we check N signs
• Space complexity: \(O(N)\)
  • Memory for storing sign information

Implementation Notes

• Use a set for the candidate R values to avoid duplicates

• Since R is a non-negative integer, skip negative values

• The effect is guaranteed to always be non-negative, but an explicit check is unnecessary (per the problem statement)

• Since sign coordinates can be negative, comparisons must be done using absolute values

  Source Code

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    signs = []
    for i in range(1, n + 1):
        x, p = map(int, data[i].split())
        signs.append((x, p))
    
    max_effect = 0
    candidates = set()
    candidates.add(0)
    
    for x, p in signs:
        candidates.add(abs(x))
        candidates.add(abs(x) + 1)
    
    for R in candidates:
        if R < 0:
            continue
        total = 0
        for x, p in signs:
            if abs(x) <= R:
                total += p
        effect = total - R * R
        if effect > max_effect:
            max_effect = effect
            
    print(max_effect)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.