#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
int arr[2005][2005];
vector<ii> V;
vector<ii> L[2005],R[2005];
int memo[2005][2005];
void dfs(int x,vector<ii> v,int d){
if (x==-1 || x==n) return;
vector<ii> res;
for (auto [l,r]:v){
rep(y,l,r+1) if (arr[x][y]==0){
if (!res.empty() && res.back().se+1==y) res.back().se++;
else res.pub({y,y});
}
}
for (auto it:res) V.pub(it);
dfs(x+d,res,d);
}
signed biggest_stadium(signed N, std::vector<std::vector<signed>> F){
n=N;
rep(x,0,n) rep(y,0,n) arr[x][y]=F[x][y];
int ans=0;
rep(x,0,n){
vector<ii> v;
rep(y,0,n) if (arr[x][y]==0){
if (!v.empty() && v.back().se+1==y) v.back().se++;
else v.pub({y,y});
}
V=v;
dfs(x-1,v,-1);
dfs(x+1,v,1);
sort(all(V),[](ii i,ii j){
if ((i.se-i.fi)==(j.se-j.fi)) return i>j;
else return i.se-i.fi<j.se-j.fi;
});
vector<iii> res;
for (auto it:V){
if (!res.empty() && res.back().fi==it) res.back().se++;
else res.pub({it,1});
}
//for (auto it:res) cout<<it.fi.fi<<" "<<it.fi.se<<" "<<it.se<<endl;
//cout<<endl;
rep(x,0,n) L[x].clear(),R[x].clear();
for (auto it:res){
L[it.fi.fi].pub({it.fi.se,it.se});
R[it.fi.se].pub({it.fi.fi,it.se});
}
rep(x,0,n+1) rep(y,x,n+1) memo[x][y]=0;
rep(l,0,n+1) rep(x,0,n-l+1){
int y=x+l;
if (x!=0){
int t=memo[x][y];
for (auto it:L[x]) if (y<=it.fi) t+=(min(it.fi,y)-x+1)*it.se;
memo[x-1][y]=max(memo[x-1][y],t);
}
if (y!=n){
int t=memo[x][y];
for (auto it:R[y]) if (it.fi<=x) t+=(y-max(it.fi,x)+1)*it.se;
memo[x][y+1]=max(memo[x][y+1],t);
}
}
ans=max(ans,memo[0][n]);
//rep(x,0,n+1){
//rep(y,0,n+1) cout<<memo[x][y]<<" "; cout<<endl;
//}
//cout<<endl;
}
return ans;
}
