【CODEFORCES】C. Gargari and Bishops

C. Gargari and Bishops
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.
He has a n × n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops Gargari will get x dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.
We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).
Input
The first line contains a single integer n (2 ≤ n ≤ 2000). Each of the next n lines contains n integers aij (0 ≤ aij ≤ 109) — description of the chessboard.
Output
On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n), where xi is the number of the row where the i-th bishop should be placed, yi is the number of the column where the i-th bishop should be placed. Consider rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right.
If there are several optimal solutions, you can print any of them.
Sample test(s)
input

4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1

output

12
2 2 3 2

문제풀이: 이 문제는 문제 데이터가 많지 않은 것을 보고 먼저 일일이 열거할 생각을 했는데 이렇게 썼어요.
2개의 상은 한 세포를 동시에 공격할 수 없지만 최대와 함께 해야 한다. 우리는 왼쪽 대각선과 또 대각선의 두 개의 합을 처리하고 L[I]와 R[I]에 존재한다. 그리고 바둑판을 I+J로 나누어 홀수와 I+J를 짝수로 하는 두 가지 상황을 분리하여 최대치를 추출하고 마지막에 출력을 기록하면 된다.
바둑판을 나누는 방법은 너무 교활하다...
X1 Y1 X2 Y2를 미리 처리해야 합니다. 그렇지 않으면 마지막에 0 0 0 0이 출력됩니다.(판단할 때 크면 안 쓰는 것 같다)

#include <iostream>
#include <cstdio>

using namespace std;

long long l[4002],r[4002];
long long  a[2002][2002],n,i,x2,x1,y2,y1,j;
int main()
{
    scanf("%I64d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) scanf("%I64d",&a[i][j]);
    //
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
    {
        l[n-j+i]+=a[i][j];
        r[i+j-1]+=a[i][j];
    }
    x1=1; y1=1;
    x2=1; y2=2;
    long long max1=0,max2=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if ((i+j)%2!=0 && max1<l[n-j+i]+r[i+j-1]-a[i][j])
        {
            max1=l[n-j+i]+r[i+j-1]-a[i][j];
            x1=i;  y1=j;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if ((i+j)%2==0 && max2<l[n-j+i]+r[i+j-1]-a[i][j])
        {
            max2=l[n-j+i]+r[i+j-1]-a[i][j];
            x2=i; y2=j;
        }
    cout <<max1+max2<<endl;
    cout <<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
    return 0;
}