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的棋盤，每個方格中有一個非負(fù)整數(shù)，在棋盤中放兩個象，使得這兩個象既不會互相攻擊，攻擊范圍也不能有重合，并且在這兩個象攻擊范圍內(nèi)的格子中的值的總和最大，輸出總和和兩個象的位置坐標(biāo)。如果一個格子和象在一條對角線上，則這個格子就在這個象的攻擊范圍內(nèi)。 分析：簡單分析可以得出：位于同一條主對角線上元素Map[i][j]滿足i-j相同，位于同一條副對角線上的元素Map[i][j]滿足i+j相同。如果兩個象不會互相攻擊，且攻擊范圍沒有重合，那么這兩個象的坐標(biāo)x1+y1和x2+y2的奇偶性一定不同。所以我們只需預(yù)處理出每條對角線上的元素之和，然后更新即可。具體見代碼。
#include<cstdio> #include<cstring> const int N = 2005; typedef long long LL; LL Map[N][N]; //棋盤 LL L[N*2]; //副對角線元素之和 LL R[N*2]; //主對角線元素之和 int main() {int n;while(~scanf("%d",&n)) {memset(L, 0, sizeof(L));memset(R, 0, sizeof(R));for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {scanf("%I64d",&Map[i][j]);L[i+j] += Map[i][j]; //同一條副對角線i+j相同R[i-j+n] += Map[i][j]; //同一條主對角線i-j相同}}int x1 = 1, x2 = 1, y1 = 1, y2 = 2;LL max1 = 0, max2 = 0;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {LL tmp = L[i+j] + R[i-j+n] - Map[i][j];if((i+j) % 2 == 0 && tmp > max1) {max1 = tmp;x1 = i;y1 = j;}if((i + j) % 2 == 1 && tmp > max2) {max2 = tmp;x2 = i;y2 = j;}}}printf("%I64d\n", max1 + max2);printf("%d %d %d %d\n", x1, y1, x2, y2);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForce 463C Gargari and Bishops（贪心+暴力）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。