Codeforces Round #264 (Div. 2)C（找規律）

Codeforces Round #264 (Div. 2)C（找規律）

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~