#include "soccer.h"
#pragma GCC optimize("O3,unroll-loops")
#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];
int dp[lim][lim];
pii precalc[lim][lim];
vector<pii>have[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]});
}
}
int nextind[n][n+1];
for(int i=0;i<n;i++){
nextind[i][n]=n;
for(int j=n-1;0<=j;j--){
if(j!=n-1){
nextind[i][j]=nextind[i][j+1];
}else{
nextind[i][j]=n;
}
if(a[i][j]){
nextind[i][j]=j;
}
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cerr<<nextind[i][j]<<' ';
// }cerr<<'\n';
// }cerr<<'\n';
int ans=0;
for(int i=0;i<n;i++){
int gsz=0;
for(int j=0;j<=n;j++){
for(auto[x,y]:have[j]){
dp[x][y]=0;
}
have[j].clear();
}
// cerr<<"at mid "<<i<<'\n';
auto insert=[&](pii x,int val) -> void {
if(!dp[x.first][x.second]){
have[x.second-x.first].pb(x);
assert(++gsz<=6000);
}
dp[x.first][x.second]=max(dp[x.first][x.second],val);
// cerr<<"left\n";
};
auto trans=[&](pii x,int plim,int past) -> void {
if(x.second<x.first)return;
if(!dp[x.first][x.second])precalc[x.first][x.second]=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)*
(precalc[x.first][x.second].second-precalc[x.first][x.second].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[x,y]:have[sz]){
int val=dp[x][y];
ans=max(ans,val);
// cerr<<x<<' '<<y<<" :: "<<val<<'\n';
pii stuck=precalc[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;
int p=nextind[j][last+1];
// cerr<<p<<" is p\n";
while(p<=y){
// cerr<<"add "<<last+1<<' '<<p-1<<" because "<<j<<'\n';
trans({last+1,p-1},did,val);
last=p;
p=nextind[j][p+1];
}
trans({last+1,y},did,val);
}
}
}
// cerr<<'\n';
}
return ans;
}
