【題解】Codeforces 463C. Gargari and Bishops

#include <bits/stdc++.h>
using namespace std;

long long n, g[2005][2005], l[4005], r[4005];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> g[i][j];
            l[i-j+2000] += g[i][j];
            r[i+j] += g[i][j];
        }
    }
    long long tot[2] = {}, x[2] = {1, 1}, y[2] = {1, 2};
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            int tmp = (i+j)%2;
            long long t = l[i-j+2000]+r[i+j]-g[i][j];
            if (t > tot[tmp]){
                tot[tmp] = t;
                x[tmp] = i;
                y[tmp] = j;
            }
        }
    }
    cout << tot[0]+tot[1] << "\n";
    cout << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << "\n";
}