3 seconds
256 megabytes
standard input
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).
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.
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.
4 1 1 1 1 2 1 1 0 1 1 1 0 1 0 0 1
12 2 2 3 2
题意：在一个NxN的棋盘上都放有数字，有两个主教，只要是和主教在同一条对角线上的数字都会被加在一起，并且这两个主教攻击范围不能重合，问你怎样放这两个主教才能使两个主教的总共和最大
解题思路：只要是同一条主对角线（左斜方向）他们的行列标号之差一定相同，只要是同一条副对角线（右斜方向）他们的行列标号之和一定相同，所以我们可以先预处理所有对角线，在计算！
AC代码：
//注意此题数据量较大，不要使用cin和cout不然一定TLE #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<queue> #include<algorithm> #define LL long long #define IT __int64 const int Max=2100; IT s[Max][Max]; IT x[Max*2]; IT y[Max*2]; using namespace std; int main() { int n,i,j; int x1,y1,x2,y2; IT sum,max_x,max_y; while(scanf("%d",&n)!=EOF) { memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(s,0,sizeof(s)); sum=0; max_x=0; max_y=0; x1=1; y1=1; x2=1; y2=2; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%I64d",&s[i][j]); x[i-j+n]+=s[i][j]; y[i+j]+=s[i][j]; } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { LL res=x[i-j+n]+y[i+j]-s[i][j]; if((i+j)&1) { if(max_x<res) { max_x=res; x2=i; y2=j; } } else { if(max_y<res) { max_y=res; x1=i; y1=j; } } } } sum=max_x+max_y; printf("%I64d\n",sum); //cout<<sum<<endl; printf("%d %d %d %d\n",x1,y1,x2,y2); //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl; } return 0; }