← 返回题目列表

AtCoder · tupc2023_a

A. 南北线/东西线

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

配点 : 100 点

背景

仙台有两条线路,南北线和东西线,以仙台站为中心。 2 有地铁线。 ( 维基百科/仙台市地铁 )

問題文

2 维度平面上 有 N 个城市。 第i 个城市是坐标 它位于 (x_i, y_i) ,人口为 p_i 人。

您选择一个城市并使用所选城市作为基点( x 东西方向(平行于轴线) y 我正在考虑建造一条在南北方向(平行于轴线)无限延伸的地铁。

通过选择合适的城市,找出可以使用地铁的最大人数。 然而,可以乘坐地铁的人是指居住在有地铁服务的城市的所有人。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq x_i, y_i \leq 2 \times 10^5
  • 1 \leq p_i \leq 10^9
  • (x_i, y_i) \neq (x_j, y_j) \, (i \neq j)
  • 输入全部为整数

入力

输入将以以下形式从标准输入给出。

N
x_1 y_1 p_1
x_2 y_2 p_2
\vdots
x_N y_N p_N

出力

请输出可乘坐地铁的最大人数。 如果选择第


入力例 1

4
10 7 40
12 12 50
5 7 10
5 10 30

出力例 1

80

3 个城市,则直线 x = 5, y = 7 上面将修建地铁。 此时,这座城市 住在 1 、都市 3 、都市 4 住在 40 + 10 + 30 = 80 人们可以使用地铁,这是最大值。 请注意,您无法从


入力例 2

5
1 1 1
1 2 1
2 2 1
2 3 1
3 3 1

出力例 2

3

座標 (1, 3) 开始建造地铁。


入力例 3

15
3 5 636708929
2 8 994903426
9 9 607399553
8 8 827889418
9 5 668774629
3 9 811132635
10 7 890433514
5 6 742283973
1 1 912497044
4 9 946700459
1 4 730139009
1 9 843207307
7 4 728535529
2 4 950182766
9 1 523704155

出力例 3

4851076007

答案是 32 bit 它可能不适合整数类型。 写入直到