← 返回题目列表

AtCoder · awc0053_c

C. 无线电塔的覆盖范围

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

Takahashi 正在沿着直路寻找接收信号总强度最大的点。

道路用数轴表示,坐标增加的方向称为右,坐标减少的方向称为左。有 N 沿路安装的无线电塔,编号为Tower 1,塔 2, \ldots,塔 N。塔 i 建立在坐标处 X_i,满意 X_1 \leq X_2 \leq \cdots \leq X_N (同一坐标上可以建造多个塔)。

来自塔的无线电波 i 达到的距离 L_i 向左, R_i 塔位置右侧。也就是说,它覆盖了从坐标到的范围 X_i - L_i 协调 X_i + R_i,包括在内。当位于塔楼覆盖范围内时 i,可以接收到的信号强度为 C_i.

高桥会选择并站在道路上具有整数坐标的任意单个点(也允许负坐标)。当高桥站在坐标上时 p (整数),他能接收到的信号总强度为

\displaystyle\sum_{\substack{1 \leq i \leq N \\ X_i - L_i \leq p \leq X_i + R_i}} C_i

即覆盖范围内所有塔的信号强度之和 p。如果所选点不在任何发射塔的覆盖范围内,则总信号强度为 0.

求高桥在最佳选择站立位置时可以接收到的最大总信号强度。

约束

  • 1 \leq N \leq 10^5
  • 0 \leq X_i \leq 10^9
  • X_1 \leq X_2 \leq \cdots \leq X_N
  • 0 \leq L_i \leq 10^9
  • 0 \leq R_i \leq 10^9
  • 1 \leq C_i \leq 10^4
  • 所有输入均为整数。

输入

N
X_1 L_1 R_1 C_1
X_2 L_2 R_2 C_2
\vdots
X_N L_N R_N C_N

第一行包含一个整数 N 代表无线电塔的数量。的 i- 以下各项 N 行 (1 \leq i \leq N) 包含坐标 塔的 X_i 塔的 i,距离 L_i 无线电波到达左边,距离 R_i 无线电波到达右侧,信号强度 C_i,用空格分隔。

输出

以单行整数形式输出高桥可以接收的最大总信号强度。


示例输入 1

3
2 1 2 5
5 2 0 4
6 1 1 3

示例输出 1

9

示例输入 2

4
0 0 0 7
0 1 2 3
3 1 0 5
10 0 0 1

示例输出 2

10

示例输入 3

8
1 1 0 2
4 2 3 5
6 0 2 4
8 3 1 6
10 5 0 3
10 0 4 7
13 2 2 1
20 10 0 8

示例输出 3

18

示例输入 4

15
0 0 5 2
2 1 2 4
4 3 0 6
7 2 5 3
9 0 0 8
12 4 1 5
15 5 5 7
18 3 2 4
18 0 6 9
23 10 0 1
25 2 3 6
30 8 4 5
35 0 0 10
40 7 7 2
50 20 0 8

示例输出 4

21

示例输入 5

1
1000000000 1000000000 1000000000 10000

示例输出 5

10000