#include "soccer.h"
#include<bits/stdc++.h>


int a[2005][2005];
int h[2005][2005],c[2005][2005];
bool chkmax(int &a,int b){return a<b?a=b,1:0;}
bool chkmin(int &a,int b){return a>b?a=b,1:0;}
int xl[2005],xr[2005],xc[2005];
int tr[2005][2005];
const int inf=0x3f3f3f3f;
int ml[2005],mr[2005];
std::vector<int> ad[2005],dl[2005];
int mx[2005][2005],mn[2005][2005];
std::bitset<2005>ok;
int f[2005][2005];
int biggest_stadium(int n, std::vector<std::vector<int>> field)
{
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		a[i][j]=!field[i-1][j-1];
		h[i][j]=h[i][j-1]+!a[i][j];
		c[i][j]=c[i-1][j]+!a[i][j];
	}
	bool allc=1;
	int s=0;
	for(int i=1;i<=n;++i){
		xl[i]=n+1,xr[i]=0;xc[i]=0;
		for(int j=1;j<=n;++j){
			if(a[i][j]){
				xr[i]=j;
				if(xl[i]==n+1)xl[i]=j;
				++xc[i];
			}
		}	
		if(xc[i] && xc[i]!=xr[i]-xl[i]+1)allc=0;
		s+=xc[i];
	}
	if(!s)return 0;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		if(!(xl[i]<=xl[j] && xr[j]<=xr[i]) && !((xl[j]<=xl[i] && xr[i]<=xr[j]))){allc=0;}
	}
	int mr=0,ml=n+1,mid=0;
	for(int i=1;i<=n;++i){
		if(chkmax(mr,xr[i]))mid=i;
		if(chkmin(ml,xl[i]))mid=i;
	}
	for(int i=mid;i>1;--i)if(xr[i]<xr[i-1] || xl[i]>xl[i-1])allc=0;
	for(int i=mid;i<n;++i)if(xr[i]<xr[i+1] || xl[i]>xl[i+1])allc=0;
	if(allc){return s;}
	for(int i=1;i<=n;++i){
		xl[i]=n+1;xr[i]=0;
	}
	int l=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;){
			while(j<=n && !a[i][j])++j;
			if(j>n)break;
			int r=j;
			while(r<n && a[i][r+1])++r;
			tr[i][j]=r;
			ad[j].emplace_back(i);
			dl[r+1].emplace_back(i);
			++l;
			j=r+1;
		}
	}
	if(n>500 && l>n+1)return 0;
	int ans=0;
	for(int j=1;j<=n;++j){
		for(auto i:dl[j]){
			ok[i]=0;
		}
		for(auto i:ad[j]){
			ok[i]=1;
			xl[i]=j;xr[i]=tr[i][j];
			mn[i][i]=xr[i];
			mx[i][i]=xl[i];
			f[i][i]=xr[i]-xl[i]+1;
			for(int l=i;ok[l];--l)for(int r=i;ok[r];++r){
				if(l==i&&r==i)continue;	
				mn[l][r]=std::min(mn[l+1][r],xr[l]);
				mx[l][r]=std::max(mx[l+1][r],xl[l]);
				f[l][r]=std::max(f[l][r-1],f[l+1][r])+(mn[l][r]-mx[l][r]+1);
			}
			int l=i,r=i;
			while(ok[l-1])--l;
			while(ok[r+1])++r;
			chkmax(ans,f[l][r]);
		}
	}
	return ans;
}