#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int n;
int a[N][N];
int top[N][N],bot[N][N],pre[N][N][2];
vector<pair<int,int>> rect[N];
int ans;
map<tuple<int,int,int,int>,int> mem;
map<tuple<int,int,int,int>,bool> vis;
int& get(int i,int j){
int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
return mem[{l,r,t,b}];
}
int biggest_stadium(int _n,vector<vector<int>> _a){
n=_n;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=_a[i-1][j-1]^1;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)top[i][j]=a[i][j]?min(i,i>1?top[i-1][j]:n+1):n+1;
for(int i=n;i>=1;i--)for(int j=1;j<=n;j++)bot[i][j]=a[i][j]?max(i,bot[i+1][j]):0;
for(int i=1;i<=n;i++){
int t=0,b=n+1;
for(int j=1;j<=n;j++){
for(int x=0;x<2;x++)pre[i][j][x]=a[i][j]==x?j:pre[i][j-1][x];
if(a[i][j]){
if(a[i][j-1]){
top[i][j]=max(top[i][j],top[i][j-1]);
bot[i][j]=min(bot[i][j],bot[i][j-1]);
}
rect[j-pre[i][j][0]].emplace_back(i,j);
}
}
}
for(int w=n;w>=1;w--)for(auto [i,j]:rect[w]){
int l=pre[i][j][0]+1,r=j,t=top[i][j],b=bot[i][j];
if(vis[{l,r,t,b}])continue;
vis[{l,r,t,b}]=true;
int h=b-t+1;
int res=w*h+get(i,j);
ans=max(ans,res);
if(t>1){
for(int nr=pre[t-1][r][1],nl;nr>=l;nr=pre[t-1][nl][1]){
nl=max(l-1,pre[t-1][nr][0]);
int p=nl>=l?t-1:i;
get(p,nr)=max(get(p,nr),res-(nr-nl)*h);
}
}
if(b<n){
for(int nr=pre[b+1][r][1],nl;nr>=l;nr=pre[b+1][nl][1]){
nl=max(l-1,pre[b+1][nr][0]);
int p=nl>=l?b+1:i;
get(p,nr)=max(get(p,nr),res-(nr-nl)*h);
}
}
}
return ans;
}
