C. Gargari and Bishops time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output
Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.
He has a n?×?n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops Gargari will get x dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.
We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).
Input
The first line contains a single integer n (2?≤?n?≤?2000). Each of the next n lines contains n integers aij (0?≤?aij?≤?109) ― description of the chessboard.
Output
On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: x1,?y1,?x2,?y2 (1?≤?x1,?y1,?x2,?y2?≤?n), where xi is the number of the row where the i-th bishop should be placed, yi is the number of the column where the i-th bishop should be placed. Consider rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right.
If there are several optimal solutions, you can print any of them.
Sample test(s) input
4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1
output
12
2 2 3 2
题意：在n*n的矩阵中选两个点，要求这两个点所覆盖的点的总和最大，且它们分别覆盖的点不能有相同的，一给点能被另一个点覆盖当且仅当它们在同一斜线上
思路：既然要求覆盖的点不能有相同的，假设一个点为（i ， j ），令v=i+j，那么这两个点的v值一定一个是奇数，一个是偶数，否则无论怎么选都会有相同的点被覆盖，所以只
需要预处理出矩阵每个斜行数（左斜，右斜）的总和，然后遍历一遍矩阵的点，分点的v值为奇数和偶数分别记录最大值即可，很容易想到这个思路，但是处理起来觉得 略麻烦，看来还是我的代码能力不够，sad~