AT_tupc2023_a.Namboku / Tozai Line

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维平面上有 $N$ 个城市。第 $i$ 个城市位于坐标 $(x_i, y_i)$ ，人口为 $p_i$ 。

你需要从中选择一个城市，将该城市作为基点，沿着与 $x$ 轴平行（东西方向）和 $y$ 轴平行（南北方向）各修建一条无限延伸的地铁线。

请通过适当选择基点城市，求能乘坐地铁的最大人数。这里，能乘坐地铁的人是指所有在地铁经过的城市中的人口总数（即所有在地铁经过的城市中居住的人）。

输入格式

输入以如下格式从标准输入读入。

$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
```
输入#2
```
5
1 1 1
1 2 1
2 2 1
2 3 1
3 3 1
```
输出#2
```
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

说明/提示

背景

在仙台，以仙台站为中心有两条地铁线路，分别是南北线和东西线。（wikipedia / 仙台市地下铁）

样例解释 1

如果选择第 $3$ 个城市作为基点，则会沿直线 $x = 5, y = 7$ 建设地铁。此时，城市 $1$ 、城市 $3$ 、城市 $4$ 上居住的人口 $40 + 10 + 30 = 80$ 人都可以使用地铁，这就是最大值。

样例解释 2

请注意，无法以坐标 $(1, 3)$ 作为基点建设地铁。

样例解释 3

注意，答案可能超过 $32$ 位整数的范围。

数据范围

$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)$
所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页