CF463C Gargari and Bishops

Gargari 因为他的朋友 Caisa 赢了上一道题的游戏而嫉妒。他想证明自己才是天才。 他有一个 $ n \times n $ 的国际象棋棋盘。棋盘的每个格子上都写有一个数字。Gargari 想要在棋盘上放置两个主教，使得没有任何格子同时被这两个主教攻击。对于一个写有数字 $ x $ 的格子，如果该格子被某个主教攻击到，Gargari 就能获得 $ x $ 美元。请你告诉 Gargari，如何放置主教，才能获得最多的钱。 我们认为，如果某个格子与主教处于同一条对角线上（主教所在的格子也算被他自己攻击），则该格子被这个主教攻击。

第一行包含一个整数 $ n $，$ (2 \leq n \leq 2000) $。接下来的 $ n $ 行，每行包含 $ n $ 个整数 $ a_{ij} $，$ (0 \leq a_{ij} \leq 10^{9}) $，描述棋盘上的数字。

第一行输出 Gargari 能获得的最大金额。 第二行输出四个整数：$ x_{1}, y_{1}, x_{2}, y_{2} $，$ (1 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq n) $，分别表示第一个主教和第二个主教应放置的行号和列号。行号从上到下为 $1$ 到 $n$，列号从左到右为 $1$ 到 $n$。 如果有多种最优解，你可以输出其中任意一种。

由 ChatGPT 5 翻译