102985: [Atcoder]ABC298 F - Rook Score
Description
Score : $500$ points
Problem Statement
We have a grid with $10^9$ rows and $10^9$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.
For $i=1,2,\ldots,N$, a positive integer $x_i$ is written on $(r_i,c_i)$. On the other $10^{18}-N$ squares, $0$ is written.
You choose a square $(R,C)$ and compute the sum $S$ of the integers written on the $2 \times 10^9 - 1$ squares that share a row or column with $(R,C)$.
Find the maximum possible value of $S$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq r_i,c_i,x_i \leq 10^9$
- $(r_i,c_i) \neq (r_j,c_j)$ if $i \neq j$.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $r_1$ $c_1$ $x_1$ $\vdots$ $r_N$ $c_N$ $x_N$
Output
Print the answer.
Sample Input 1
4 1 1 2 1 2 9 2 1 8 3 2 3
Sample Output 1
20
If you choose $(2,2)$ as $(R,C)$, then $S$ will be $20$, which is the maximum possible value.
Sample Input 2
1 1 1000000000 1
Sample Output 2
1
Sample Input 3
15 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 450968417 430302156 982631932 161735902 880895728 923078537 707723857 189330739 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 650287940 839296263 462224593 492601449 384836991 191890310 576823355 782177068 404011431 818008580 954291757 160449218 155374934 840594328 164163676
Sample Output 3
1510053068
Input
题意翻译
在 $10^9\times10^9$ 平面上有 $n$ 个点有大于零的值，其余的点均为 $0$。现在你选择一个点，使得所在列的所有值的和，加上所在的行的所有值的和，减去当前点的值最大。求这个最大值。 translated by 月。Output
问题描述
我们有一个包含$10^9$行和$10^9$列的网格。让$(i,j)$表示从顶部数第$i$行，从左数第$j$列的方格。
对于$i=1,2,\ldots,N$，一个正整数$x_i$写在$(r_i,c_i)$上。在其他$10^{18}-N$个方格上，写上0。
你选择一个方格$(R,C)$，并计算与$(R,C)$共享一行或一列的$2 \times 10^9 - 1$个方格上的整数之和$S$。
找到$S$的最大可能值。
约束
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq r_i,c_i,x_i \leq 10^9$
- 如果$i \neq j$，则$(r_i,c_i) \neq (r_j,c_j)$。
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出：
$N$ $r_1$ $c_1$ $x_1$ $\vdots$ $r_N$ $c_N$ $x_N$
输出
打印答案。
样例输入1
4 1 1 2 1 2 9 2 1 8 3 2 3
样例输出1
20
如果你选择$(2,2)$作为$(R,C)$，那么$S$将是20，这是最大可能值。
样例输入2
1 1 1000000000 1
样例输出2
1
样例输入3
15 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 450968417 430302156 982631932 161735902 880895728 923078537 707723857 189330739 910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016 650287940 839296263 462224593 492601449 384836991 191890310 576823355 782177068 404011431 818008580 954291757 160449218 155374934 840594328 164163676
样例输出3
1510053068