#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 calc(int x,int l,int r,int w)
{
    if(x<1 || x>n) return w*(r-l+1);int res=dp[x][r][0]-(r-o[x][r][0])*w;
    for(int i=l;i<o[x][r][0];i=o[x][i][1]+1)
        res=max(res,dp[x][i][1]-(o[x][i][1]-i)*w);return res+w*(r-l+1);
}
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,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;
        dp[x][y][fl]=max(calc(o1[x][y][fl]-1,l,r,w),calc(o2[x][y][fl]+1,l,r,w));
        ans=max(ans,dp[x][y][fl]);
    }return ans;
}