#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define pb push_back
#define mid ((l+r)/2)
const int N=2005;
int n,ans,a[N][N],s[N][N],o[N][N][2],o1[N][N][2],o2[N][N][2],dp[N][N][2];
struct Node {int x,y,fl;};vector<Node> vc[N];
int f(int x1,int y1,int x2,int y2)
{--x1;--y1;return s[x1][y1]-s[x1][y2]-s[x2][y1]+s[x2][y2];}
int biggest_stadium(int _n,vector<vector<int>> _a)
{
    n=_n;for(int i=0;i<n;++i) copy(_a[i].begin(),_a[i].end(),a[i+1]+1);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];
    for(int i=1,l,r;i<=n;++i)
    {
        a[i][0]=a[i][n+1]=1;o[i][n+1][1]=n+1;
        for(int j=1;j<=n;++j)
        {
            o[i][j][0]=a[i][j]?j:o[i][j-1][0];if(a[i][j]) continue;
            l=1;r=i-1;
            while(l<=r) if(f(mid,o[i][j][0]+1,i,j))
                l=mid+1;else r=mid-1;o1[i][j][0]=l;
            l=i+1;r=n;
            while(l<=r) if(f(i,o[i][j][0]+1,mid,j))
                r=mid-1;else l=mid+1;o2[i][j][0]=r;
            vc[j-o[i][j][0]].pb((Node) {i,j,0});
        }
        for(int j=n;j;--j)
        {
            o[i][j][1]=a[i][j]?j:o[i][j+1][1];if(a[i][j]) continue;
            l=1;r=i-1;
            while(l<=r) if(f(mid,j,i,o[i][j][1]-1))
                l=mid+1;else r=mid-1;o1[i][j][1]=l;
            l=i+1;r=n;
            while(l<=r) if(f(i,j,mid,o[i][j][1]-1))
                r=mid-1;else l=mid+1;o2[i][j][1]=r;
            vc[o[i][j][1]-j].pb((Node) {i,j,1});
        }
    }
    for(int i=1,x1,x2,l,r,w;i<=n;++i) for(auto [x,y,fl]:vc[i])
    {
        l=fl?y:o[x][y][0]+1;r=fl?o[x][y][1]-1:y;w=o2[x][y][fl]-o1[x][y][fl]+1;
        x1=o1[x][y][fl]-1;x2=o2[x][y][fl]+1;
        if(fl)
        {
            dp[x][y][1]=dp[x][y+1][1]+w;
            if(x1>0) dp[x][y][1]=max(dp[x][y][1],dp[x1][l][1]+w*(r-o[x1][l][1]+1));
            if(x2<=n) dp[x][y][1]=max(dp[x][y][1],dp[x2][l][1]+w*(r-o[x2][l][1]+1));
        }
        else
        {
            dp[x][y][0]=dp[x][y-1][0]+w;
            if(x1>0) dp[x][y][0]=max(dp[x][y][0],dp[x1][r][0]+w*(o[x1][r][0]-l+1));
            if(x2<=n) dp[x][y][0]=max(dp[x][y][0],dp[x2][r][0]+w*(o[x2][r][0]-l+1));
        }ans=max(ans,dp[x][y][fl]);
    }return ans;
}