解法

$o(4n^2)$
可以看出，一个点最多只能被两个不同位置（不同位置是指两个糖豆人的路线不完全相同）的糖豆人走到。
从左边界枚举不同位置的糖豆人，然后暴力走一遍。总共会遍历$4n^2$次点。
然后枚举放置的两个糖豆人，将它们走到相同的点保存下来去重。

C++ 代码

#include <iostream>
using namespace std;
const int N=1010;
int g[N][N];
int sum[N],n;
int ans[N][N];
int gg[N][N];
int dx[4]={1,-1,-1,1};
int dy[4]={1,1,-1,-1};
bool isok(int x,int y) {
    if(x<0||y<0||x>=n||y>=n) return false;
    return true;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;++i) {
        for(int j=0;j<n;++j) {
            scanf("%d",&g[i][j]);
        }
    }

    for(int i=0;i<n;++i) {
        int x=i,y=0;
        for(int j=0;j<4;++j) {
            if(i==0&&j>1 ) break;
            if(i==n-1&&j>2) break;
            while(isok(x,y)&&!(x==i&&y==0&&j==3)) {
                if(gg[x][y]) {
                   ans[gg[x][y]-1][i]-=g[x][y];
                }
                gg[x][y]=i+1;
                sum[i]+=g[x][y];
                x+=dx[j];
                y+=dy[j];
            }
            if(j<3) x=x-dx[j]+dx[j+1],y=y-dy[j]+dy[j+1];
        }
    }
    for(int i=0;i<n;++i) {
        for(int j=i+1;j<n;++j) {
            ans[i][j]+=sum[i]+sum[j];
        }
    }
    int res=sum[0];
    for(int i=0;i<n;++i) {
        for(int j=i+1;j<n;++j) {
            res=max(res,ans[i][j]);
        }
    }
    printf("%d",res);
    return 0;
}