Codeforces Round #264 (Div. 2) C. Gargari and Bishops 主教攻击

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\n",ans_a+ans_b);

    printf("%d %d %d %d\n",x1,y1,x2,y2);

    return 0;

}