http://codeforces.com/contest/463/problem/C
在一个n∗n的国际象棋的棋盘上放两个主教，要求不能有位置同时被两个主教攻击到，然后被一个主教攻击到的位置上获得得分。求得分的最大值。
黑白格分开考虑最大值即可，注意全0情况。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
int n;
const int maxn = 2500;
LL s[maxn][maxn];
LL sum[maxn*2],cha[maxn*2];
struct node{
LL fen;
int x,y;
}a[maxn*maxn/2],b[maxn*maxn/2];
int main()
{
RD(n);
clr0(sum),clr0(cha);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j){
scanf("%I64d",&s[i][j]);
sum[i+j] += s[i][j];
cha[j-i+maxn] += s[i][j];
}
int cnt_a = 0,cnt_b = 0;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j){
LL fen = sum[i+j] + cha[j-i+maxn] - s[i][j];
if((i+j)&1){
a[cnt_a++] = (node){fen,i,j};
}
else{
b[cnt_b++] = (node){fen,i,j};
}
}
LL ans_a = -1,ans_b = -1;
int x1,y1,x2,y2;
for(int i = 0;i < cnt_a;++i){
if(ans_a < a[i].fen){
ans_a = a[i].fen;
x1 = a[i].x,y1 = a[i].y;
}
}
for(int i = 0;i < cnt_b;++i){
if(ans_b < b[i].fen){
ans_b = b[i].fen;
x2 = b[i].x,y2 = b[i].y;
}
}
printf("%I64d
",ans_a+ans_b);
printf("%d %d %d %d
",x1,y1,x2,y2);
return 0;
}