Overview

Consider each radio tower as having a coverage interval \([X_i-L_i,\;X_i+R_i]\) with weight \(C_i\).
The problem asks us to find the maximum value of “the sum of weights of intervals overlapping at some coordinate.”
As a classic interval addition problem, this can be solved efficiently using event scanning (1D sweep line / imos method).

Analysis

It is impossible to naively check “all coordinates.” Coordinates can be up to \(10^9\) and can also extend into negative values, so an array-based approach is infeasible.

So what should we look at?
The weight sum only changes at the start point and just after the end point of each interval.

• The effective interval of tower \(i\) in integer coordinates is \([left, right] = [X_i-L_i,\;X_i+R_i]\)
• To activate at a coordinate \(p\), we create events:
  • \(+C_i\) at \(left\)
  • \(-C_i\) at \(right+1\)

This way, the contribution applies exactly over the range \([left, right]\) on integer coordinates.

With this formulation, we simply process events in coordinate order, update the current value cur (the running weight sum at that coordinate), and track the maximum.

Why this is correct

The weight sum is constant in intervals without events and only changes at event coordinates.
Therefore, by applying events from left to right, we can track the values at all integer coordinates without missing any.
The maximum is obtained along the way.

Algorithm

1. For each tower:
   • \(left = X_i - L_i\)
   • \(right = X_i + R_i\)
   • Add event (left, +C_i)
   • Add event (right+1, -C_i)
2. Sort events in ascending order by coordinate.
3. For events at the same coordinate, combine them into a single delta and update cur += delta.
4. After each update, set ans = max(ans, cur).
5. Output ans.

Complexity

• Time complexity: \(O(N \log N)\) (there are \(2N\) events; sorting is the dominant factor)
• Space complexity: \(O(N)\) (event array)

Implementation Notes

• Since the interval is inclusive on both ends, it is important to place -C at right+1 for the end side.

• Because multiple events can occur at the same coordinate, it is clearer to accumulate all events at the same coordinate before updating ans, rather than updating ans one event at a time.

• The maximum total strength is around \(10^5 \times 10^4 = 10^9\), so Python’s int handles it safely.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    events = []

    for _ in range(N):
        X, L, R, C = map(int, input().split())
        left = X - L
        right = X + R
        events.append((left, C))        # add at left
        events.append((right + 1, -C))  # remove after right (inclusive interval)

    events.sort()

    cur = 0
    ans = 0
    i = 0
    m = len(events)

    while i < m:
        x = events[i][0]
        delta = 0
        while i < m and events[i][0] == x:
            delta += events[i][1]
            i += 1
        cur += delta
        if cur > ans:
            ans = cur

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.