#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include "soccer.h"
using namespace std;
int n,a[2005][2005],sum[2005][2005],nxt[2005][2005];
int f[505][505][505];
int gs(int u,int d,int l,int r){
    return sum[d][r]-sum[u-1][r]-sum[d][l-1]+sum[u-1][l-1];
}
pair<int,int> find(int p,int l,int r){
    int u=p,d=p;
    int lt=1,rt=p;
    while(lt<=rt){
        int mid=(lt+rt)/2;
        if (gs(mid,p,l,r)==0)u=mid,rt=mid-1;
        else lt=mid+1;
    }
    lt=p,rt=n;
    while(lt<=rt){
        int mid=(lt+rt)/2;
        if (gs(p,mid,l,r)==0)d=mid,lt=mid+1;
        else rt=mid-1;
    }
    return make_pair(u,d);
}
int dfs(int u,int d,int l,int r){
    if (f[u][l][r]!=-1)return f[u][l][r];
    int ans=0;
    if (l<r){
        pair<int,int> qwq=find(u,l+1,r);
        int _l=l+1,_r=r,_u=qwq.first,_d=qwq.second;
        ans=max(ans,((_d-_u+1)-(d-u+1))*(_r-_l+1)+dfs(_u,_d,_l,_r));
        _l=l,_r=l-1;
        if (u>1)_r=max(_r,nxt[u-1][l]-1);
        if (d<n)_r=max(_r,nxt[d+1][l]-1);
        _r=min(_r,r);
        if (_l<=_r){
            qwq=find(u,_l,_r);
            _u=qwq.first,_d=qwq.second;
            ans=max(ans,((_d-_u+1)-(d-u+1))*(_r-_l+1)+dfs(_u,_d,_l,_r));
        }
    }
    return f[u][l][r]=ans;
}
int biggest_stadium(int _n,vector<vector<int>> F){
    n=_n;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            a[i+1][j+1]=F[i][j];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        nxt[i][n+1]=n+1;
        for (int j=n;j>=1;j--){
            nxt[i][j]=nxt[i][j+1];
            if (a[i][j]==1)nxt[i][j]=j;
        }
    }
    memset(f,-1,sizeof(f));
    int ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (a[i][j]==0&&(j==1||a[i][j-1]==1)){
                int l=j,r=nxt[i][j]-1;
                pair<int,int> qwq=find(i,l,r);
                int u=qwq.first,d=qwq.second;
                ans=max(ans,(d-u+1)*(r-l+1)+dfs(u,d,l,r));
            }
    return ans;
}