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. Examples Input 4 1 1 1 1 2 1 1 0 1 1 1 0 1 0 0 1 Output 12 2 2 3 2 小菜鸡呀~一开始连题都没读懂 看了解析之后才明白 是我太弱 不过也算拓展知识面了 论黑白棋的摆放（保证了两个主教的对角线攻击不会相交）可画图验证。 题意是在棋盘上摆两个主教，两个主教的攻击范围是主对角线和副对角线，他们可以获得对角线上的金钱，并且规定他们的攻击范围没有交点（用黑白棋思想，在代码中可用行列相加奇偶来区分）。 因为每个主对角线上的元素行数-列数相等，每个副对角线上的元素行数加列数相等，所以可以一开始就可以（将每个点所对应的对角线上元素的和求出来) 然后再分别判断黑白个，分别求出黑格中最大值（对角线元素的和）所对应的点和白格中最大值所对应的点。相加即可，不要忘记减去一个重复元素（主对副对重合的点）。
#include<stdio.h> #include<string.h> long long a[2010][2010]; long long x[4010]; long long y[4010]; int main() { int i,j; int n,x1,x2,y1,y2; while(~scanf("%d",&n)) { memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%lld",&a[i][j]); x[i-j+n]+=a[i][j];//分别求出每个点所对应的对角线元素的和。 y[j+i]+=a[i][j]; } long long maxb=-1,maxh=-1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if((i+j)%2==1)//区分黑白 { if(maxh<x[i-j+n]+y[j+i]-a[i][j])//减去重复的点。 { maxh=x[i-j+n]+y[i+j]-a[i][j]; x1=i; y1=j; } } else{ if(maxb<x[i-j+n]+y[j+i]-a[i][j]) { maxb=x[i-j+n]+y[i+j]-a[i][j]; x2=i; y2=j; } } } printf("%lld\n",maxb+maxh); printf("%d %d %d %d\n",x1,y1,x2,y2); } return 0; }