#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];
    int tmp[N][N];
    int L[N][N],R[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];
    for (int i=0;i<=n+1;i++) a[0][i]=a[n+1][i]=a[i][0]=a[i][n+1]=1;
    if (n>500)
    {
        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) 
            {
                if (bl) return 0;
                g.push_back(mp(l,r));
            }
            else 
            {
                if (g.size()) bl=1;
            }
        }
        poly gg;

        for (auto [l,r]:g)
            for (auto [x,y]:g)
                if (!(l<=x&&y<=r||x<=l&&r<=y)) return 0;
        int mx=0;
        for (int i=0;i+1<g.size();i++)
        {
            auto [l,r]=g[i];
            auto [x,y]=g[i+1];
            if ((l<=x&&y<=r)<mx) return 0;
            mx=max(mx,int(l<=x&&y<=r));
        }
        return tot;
    }
    for (int i=1;i<=n+1;i++)
        for (int j=1;j<=n+1;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=0;i<=n+1;i++)
            for (int j=0;j<=n+1;j++)
            {
                L[i][j]=0,R[i][j]=n+1;
                tmp[i][j]=0;
            }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (aa[i-1][j-1])
                {
                    if (j<h) L[i][i]=max(L[i][i],j);
                    else R[i][i]=min(R[i][i],j);
                }
        // for (int i=1;i<=n;i++)
        //     cout<<L[i][i]<<";"<<R[i][i]<<endl;
        for (int i=n;i>=1;i--)
            for (int j=i;j<=n;j++)
            {
                L[i][j]=max({L[i+1][j],L[i][j-1],L[i][j]});
                R[i][j]=min({R[i+1][j],R[i][j-1],R[i][j]});
                // cout<<h<<" "<<i<<" "<<j<<" "<<L[i][j]<<" "<<R[i][j]<<" "<<tmp[i][j]<<endl;
                if (R[i][j]==h) continue;
                tmp[i][j]=(j-i+1)*(R[i][j]-L[i][j]-1);
                tmp[i][j]=max(tmp[i][j],tmp[i+1][j]+(R[i][j]-L[i][j]-1));
                tmp[i][j]=max(tmp[i][j],tmp[i][j-1]+(R[i][j]-L[i][j]-1));
                // cout<<h<<" "<<i<<" "<<j<<" "<<L[i][j]<<" "<<R[i][j]<<" "<<tmp[i][j]<<endl;
                ans=max(ans,tmp[i][j]);
            }
    }
    return ans;
}