Gargari and Bishops.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define MAX 100005
typedef long long int ll;

ll secondary[4001];
ll primary[4001];
pair<int,int> evenIndex;
pair<int,int> oddIndex;
ll value[2];

	int arr[2001][2001];
//value 0 denotes even
//value 1 denotes odd

int main(){
	memset(value,-1,sizeof value);
	int n;
	cin>>n;
	REP(i,n){
		REP(j,n){
			scanf("%d",&arr[i][j]);
			secondary[i+j]+=arr[i][j];
			primary[i-j+n-1]+=arr[i][j];
		}
	}
	
	ll candidate;
	REP(i,n){
		REP(j,n){
			candidate=secondary[i+j]+primary[i-j+n-1]-arr[i][j];
				
			if((i+j)&1){
				if(candidate>value[1]){
					value[1]=candidate;
					oddIndex.first=i;
					oddIndex.second=j;
				}
				
			}
			else{
				if(candidate>value[0]){
					value[0]=candidate;
					evenIndex.first=i;
					evenIndex.second=j;
				}
			}
			
		}
	}
	cout<<value[0]+value[1]<<endl;
	if(value[0]>value[1]){
		cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<" ";
		cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<endl;
	}
	else{
		cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<" ";
		cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<endl;
	}
	
	
	
}