#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=2100;
int n;
struct{
pii tree[2*lim+1];
pii query(int l,int r){
// assert(l<=r);
// cerr<<l<<' '<<r<<'\n';
int ansmin=INT_MIN;
int ansmax=INT_MAX;
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
if(l&1){
ansmin=max(ansmin,tree[l].first);
ansmax=min(ansmax,tree[l].second);
l++;
}
if(r&1){
r--;
ansmin=max(ansmin,tree[r].first);
ansmax=min(ansmax,tree[r].second);
}
}
return {ansmin,ansmax};
}
void update(int p,pii val){
tree[p+=n]=val;
for(p>>=1;p;p>>=1){
tree[p].first=max(tree[p<<1].first,tree[p<<1|1].first);
tree[p].second=min(tree[p<<1].second,tree[p<<1|1].second);
}
}
}st[lim];
map<pii,int>dp[lim];
int biggest_stadium(int N,vector<vector<int>>a){
n=N;
int haveup[n][n],havedown[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
haveup[i][j]=-1;
havedown[i][j]=n;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]){
haveup[i][j]=i;
}else if(i){
haveup[i][j]=haveup[i-1][j];
}
}
}
for(int i=n-1;0<=i;i--){
for(int j=0;j<n;j++){
if(a[i][j]){
havedown[i][j]=i;
}else if(i!=n-1){
havedown[i][j]=havedown[i+1][j];
}
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cerr<<haveup[i][j]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cerr<<havedown[i][j]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
st[i].update(j,pii{haveup[i][j],havedown[i][j]});
}
}
vector<int>inds[n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]){
inds[i].pb(j);
}
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
dp[j].clear();
}
// cerr<<"at mid "<<i<<'\n';
auto insert=[&](pii x,int val) -> void {
dp[x.second-x.first][x]=max(dp[x.second-x.first][x],val);
// cerr<<"left\n";
};
auto trans=[&](pii x,int plim,int past) -> void {
if(x.second<x.first)return;
pii lims=st[i].query(x.first,x.second);
// cerr<<x.first<<' '<<x.second<<" can go till "<<lims.first<<' '<<lims.second<<'\n';
insert(x,past+(x.second-x.first+1)*
(lims.second-lims.first-1-plim));
};
int last=-1;
for(int j=0;j<n;j++){
if(a[i][j]){
trans({last+1,j-1},0,0);
last=j;
}
}
trans({last+1,n-1},0,0);
for(int sz=n;0<=sz;sz--){
for(auto[rang,val]:dp[sz]){
auto[x,y]=rang;
// cerr<<x<<' '<<y<<" :: "<<val<<'\n';
ans=max(ans,val);
pii stuck=st[i].query(x,y);
int did=stuck.second-stuck.first-1;
for(int j:{stuck.first,stuck.second}){
// cerr<<j<<'\n';
if(j<0||n<=j)continue;
last=x-1;
auto p=upper_bound(inds[j].begin(),inds[j].end(),last);
while(p!=inds[j].end()&&*p<=y){
// cerr<<"add "<<last+1<<' '<<(*p)-1<<" because "<<j<<'\n';
trans({last+1,(*p)-1},did,val);
last=*p;
p++;
}
trans({last+1,y},did,val);
}
}
}
// cerr<<'\n';
}
// for(int i=0;i<n;i++){
// int dp[n][n]{};
// for(int sz=n;sz;sz--){
// for(int l=0;l<=n-sz;l++){
// int r=l+sz-1;
// if(updp[i][l][r]<=downdp[i][l][r]){
// dp[l][r]=(r-l+1)*(downdp[i][l][r]-updp[i][l][r]+1);
// }
// if(l&&dp[l-1][r]){
// dp[l][r]=max(dp[l][r],
// dp[l-1][r]+(r-l+1)*(downdp[i][l][r]-downdp[i][l-1][r]+updp[i][l-1][r]-updp[i][l][r]));
// }
// if(r+1<n&&dp[l][r+1]){
// dp[l][r]=max(dp[l][r],
// dp[l][r+1]+(r-l+1)*(downdp[i][l][r]-downdp[i][l][r+1]+updp[i][l][r+1]-updp[i][l][r]));
// }
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// ans=max(ans,dp[i][j]);
// }
// }
// }
return ans;
}
