概要

各電波塔のカバー区間 \([X_i-L_i,\;X_i+R_i]\) に重み \(C_i\) が乗っていると考え、
「ある座標で重なっている区間の重み和」の最大値を求める問題です。
区間加算の典型として、イベント走査（いもす法の一次元版）で高速に解けます。

考察

愚直に「全座標」を調べるのは不可能です。座標は最大で \(10^9\)、さらに負にも広がるため、配列で持つ方法は使えません。

では何を見るべきか？
重み和が変化するのは、各区間の開始点と終了直後だけです。

• 塔 \(i\) の有効区間は整数座標で \([left, right] = [X_i-L_i,\;X_i+R_i]\)
• ある座標 \(p\) で有効にしたいので、
  
  • \(left\) で \(+C_i\)
  • \(right+1\) で \(-C_i\) とイベント化すれば、整数座標上でちょうど \([left,right]\) の間だけ寄与します。

この形にすると、あとは座標順にイベントを処理して現在値 cur（その座標以降の重み和）を更新し、最大値を取るだけです。

なぜこれで正しいか

重み和はイベントがない区間では一定で、イベント座標でのみ変化します。
よって、イベントを左から順に反映していけば、全ての整数座標での値を漏れなく追跡できます。
最大値もその途中で得られます。

アルゴリズム

1. 各塔について
   • \(left = X_i - L_i\)
   • \(right = X_i + R_i\)
   • イベント (left, +C_i) を追加
   • イベント (right+1, -C_i) を追加
2. イベントを座標で昇順ソートする。
3. 同じ座標のイベントはまとめて delta として合算し、cur += delta。
4. 各更新後に ans = max(ans, cur) とする。
5. ans を出力。

計算量

• 時間計算量: \(O(N \log N)\)（イベント数は \(2N\)、ソートが支配的）
• 空間計算量: \(O(N)\)（イベント配列）

実装のポイント

• 区間が 両端含む なので、終了側は right+1 に -C を置くのが重要です。

• 同じ座標に複数イベントが来るため、1つずつ ans 更新するより、同座標をまとめて加算してから更新すると扱いが明確です。

• 強度合計は最大で \(10^5 \times 10^4 = 10^9\) 程度なので、Python の int なら安全です。

  ソースコード

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

この解説は gpt-5.3-codex によって生成されました。