#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],o1[N][N],o2[N][N],dp[N][N];
struct Node {int x,y;};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) for(int j=1;j<=n;++j)
    {
        o[i][j]=a[i][j]?j:o[i][j-1];if(a[i][j]) continue;
        l=1;r=i-1;while(l<=r) if(f(mid,o[i][j]+1,i,j)) l=mid+1;else r=mid-1;o1[i][j]=l;
        l=i+1;r=n;while(l<=r) if(f(i,o[i][j]+1,mid,j)) r=mid-1;else l=mid+1;o2[i][j]=r;
        vc[j-o[i][j]].pb((Node) {i,j});
    }
    for(int i=1,x1,x2,l,r,w;i<=n;++i) for(auto [x,y]:vc[i])
    {
        l=o[x][y]+1;r=y;w=o2[x][y]-o1[x][y]+1;x1=o1[x][y]-1;x2=o2[x][y]+1;
        dp[x][y]=dp[x][y-1]+w;
        if(x1>0) dp[x][y]=max(dp[x][y],dp[x1][r]+w*(o[x1][r]-l+1));
        if(x2<=n) dp[x][y]=max(dp[x][y],dp[x2][r]+w*(o[x2][r]-l+1));
        ans=max(ans,dp[x][y]);
    }return ans;
}