CF1221F Choose a Square

Petya 最近发现了一个名为“选择正方形”的游戏。在这个游戏中，有 $n$ 个点，编号从 $1$ 到 $n$，分布在一张无限大的平面上。第 $i$ 个点的坐标为 $(x_i, y_i)$，其权值为 $c_i$。 你需要选择一个正方形，使得其边平行于坐标轴，下左角和上右角都在直线 $y = x$ 上，且所有角的坐标均为整数。 你的得分为被所选正方形覆盖的所有点的权值之和减去正方形的边长。注意，边长可以为零。 Petya 想让你计算在只选一个正方形的情况下，所能获得的最大得分。

输入的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示平面上的点的数量。 接下来的 $n$ 行，每行包含三个整数 $x_i, y_i, c_i$（$0 \le x_i, y_i \le 10^9, -10^6 \le c_i \le 10^6$），分别表示第 $i$ 个点的坐标和权值。

第一行输出 Petya 能获得的最大得分。 第二行输出四个整数 $x_1, y_1, x_2, y_2$（$0 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9, x_1 = y_1, x_2 = y_2, x_1 \le x_2$），用空格分隔，分别表示所选正方形的左下角和右上角的坐标，以获得最大得分。

下图对应于第一个样例： 由 ChatGPT 4.1 翻译