依据贪心能够知道，放置的教主必须不能相互攻击到（也就是不在一条对角线上）才干够使得结果最大化。

依据观察能够得到教主相互不攻击的条件是他的坐标和互为奇偶（x + y)

之后直接暴力，处理每一个坐标对角线的和就好

时间复杂度 0(n ^ 2)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn = 2005;

LL sum_l[maxn * 10] = {0},sum_r[maxn * 10] = {0};

LL mat[maxn][maxn];

int main(){

    int n,m;

    LL  x;

    scanf("%d",&n);

    for(int i = 0; i < n; i++){

        for(int j = 0; j < n; j++){

            scanf("%I64d",&mat[i][j]);

            sum_l[i + j] += mat[i][j];

            sum_r[n - 1 + j - i] += mat[i][j];

        }

    }

    //for(int i = 0; i < 2 * n - 1; i++)

    //    printf("%I64d %I64d\n",sum_l[i],sum_r[i]);

    LL max1 = - 1,max2 = -1;

    int x1,x2,y1,y2;

    for(int i = 0; i < n; i++)

        for(int j = 0; j < n; j++){

            LL ret = sum_l[i + j] + sum_r[n - 1 + j - i] - mat[i][j];

            if(((i + j) & 1) && ret > max1){

                max1 = ret;

                x1 = i;

                y1 = j;

            }

            else if((!((i + j) & 1)) && ret > max2){

                max2 = ret;

                x2 = i;

                y2 = j;

            }

        }

    LL ans = max1 + max2;

    printf("%I64d\n",ans);

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

    return 0;

}