#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 dp[N][N];
    short pos[N][N];
    short L[N][N],R[N][N];
}
int biggest_stadium(int n, std::vector<std::vector<int>> aa)
{
    int ans=0;
    vector<vector<pa>>tong(n+1,vector<pa>());
    for (int j=1;j<=n;j++)
    {
        for (int i=1;i<=n;i++)
        {
            dp[i][j]=0;
            if(aa[i-1][j-1]) pos[i][j]=i;
            else pos[i][j]=pos[i-1][j];
            tong[i-pos[i][j]].push_back(mp(i,j));
        }
    }
    for (int i=1;i<=n;i++)
    {
        L[i][0]=0;
        for (int j=1;j<=n;j++)
            if (aa[i-1][j-2]) L[i][j]=j-1;else L[i][j]=L[i][j-1];
        R[i][n+1]=n+1;
        for (int j=n;j>=1;j--)
            if (aa[i-1][j]) R[i][j]=j+1;else R[i][j]=R[i][j+1];
    }
    for (int d=1;d<=n;d++)
    {
        for (auto [i,j]:tong[d])
        {
            if (pos[i][j]!=i-1)
            {
                R[i][j]=min(R[i][j],R[i-1][j]);
                L[i][j]=max(L[i][j],L[i-1][j]);
            }
            dp[i][j]=dp[i-1][j]+R[i][j]-L[i][j]-1;
            if (L[i][j]>0)
            {
                int len=pos[i][L[i][j]]-pos[i][j];
                dp[i][j]=max(dp[i][j],dp[i][L[i][j]]+len*(R[i][j]-L[i][j]-1));
            }
            if (R[i][j]<=n)
            {
                int len=pos[i][R[i][j]]-pos[i][j];
                dp[i][j]=max(dp[i][j],dp[i][R[i][j]]+len*(R[i][j]-L[i][j]-1));
            }
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}