#include "soccer.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
#define N 2005
using namespace std;
namespace 
{
    int a[N][N],pre[505][505][505];
    int suf[505][505][505];int tmp[N][N];
    int query(int l,int r,int L,int R)
    {
        return a[r][R]-a[l-1][R]-a[r][L-1]+a[l-1][L-1];
    }
}
int biggest_stadium(int n, std::vector<std::vector<int>> aa)
{
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            a[i+1][j+1]=aa[i][j];
    if (n>30)
    {
        int nl=n,nr=0;
        bool bl=0;
        int tot=0;
        vector<pa>g;
        for (int i=1;i<=n;i++)
        {
            int l=n,r=0;
            for (int j=1;j<=n;j++)
                if (a[i][j]==0) l=min(l,j),r=max(r,j),tot++;
            for (int j=l;j<=r;j++)
                if (a[i][j]) return 0;
            if (l<=r) g.push_back(mp(l,r));
            if (l<=nl&&r>=nr)
            {
                if (bl==1) return 0;
                nl=l,nr=r;
                continue;
            }
            if (l>=nl&&r<=nr)
            {
                nl=l,nr=r;
                bl=1;
                continue;
            }
        }
        if (g.size()
        &&
        (g[0].se<g.back().fi||g.back().se<g[0].fi)) return 0;
        return tot;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            
    int ans=0;
    for (int h=1;h<=n;h++)
    {
        for (int i=1;i<=n;i++)
            for (int j=i;j<=n;j++)
                pre[1][i][j]=(query(1,1,i,j)==0&&i<=h&&h<=j)*(j-i+1);
        for (int t=2;t<=n;t++)
        {
            for (int i=n;i>=1;i--)
                for (int j=i;j<=n;j++)
                    tmp[i][j]=max({pre[t-1][i][j],tmp[i+1][j],tmp[i][j-1]});
            for (int i=1;i<=n;i++)
                for (int j=i;j<=n;j++)
                    if (query(t,t,i,j)==0)
                    {
                        pre[t][i][j]=tmp[i][j]+j-i+1;
                    }
        }
        for (int i=1;i<=n;i++)
            for (int j=i;j<=n;j++)
                suf[n][i][j]=(query(n,n,i,j)==0&&i<=h&&h<=j)*(j-i+1);
        for (int t=n-1;t>=1;t--)
        {
            for (int i=n;i>=1;i--)
                for (int j=i;j<=n;j++)
                    tmp[i][j]=max({suf[t+1][i][j],tmp[i+1][j],tmp[i][j-1]});
            for (int i=1;i<=n;i++)
                for (int j=i;j<=n;j++)
                    if (query(t,t,i,j)==0)
                    {
                        suf[t][i][j]=tmp[i][j]+j-i+1;
                    }
        }
        for (int t=1;t<=n;t++)
            for (int i=1;i<=n;i++)
                for (int j=i;j<=n;j++)
                if (query(t,t,i,j)==0)
                {
                    ans=max(ans,pre[t][i][j]+suf[t][i][j]-(j-i+1));
                    // cout<<t<<" "<<i<<" "<<j<<" "<<ans<<" "<<pre[t][i][j]<<" "<<suf[t][i][j]<<endl;
                }
    }
    return ans;
}