#include "soccer.h"

int a[2005][2005];
int dp[35][35][35][35];
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];
const int inf=0x3f3f3f3f;
int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		a[i][j]=!f[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;}
	else return 0;
	int ans=0;
	for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)for(int l=1;l<=n;++l)for(int r=l;r<=n;++r)dp[i][j][l][r]=-inf;
	for(int i=n;i;--i){
		for(int l=1;l<=n;++l)for(int r=l;r<=n;++r)
			if(h[i][r]==h[i][l-1]){
				dp[i][i][l][r]=r-l+1;
			}
		for(int j=i;j<=n;++j){
			for(int l=1;l<=n;++l)for(int r=n;r>=l;--r){
				chkmax(ans,dp[i][j][l][r]);
				chkmax(dp[i][j][l+1][r],dp[i][j][l][r]);
				chkmax(dp[i][j][l][r-1],dp[i][j][l][r]);
				if(h[i-1][r]==h[i-1][l-1])chkmax(dp[i-1][j][l][r],dp[i][j][l][r]+(r-l+1));
				if(h[j+1][r]==h[j+1][l-1])chkmax(dp[i][j+1][l][r],dp[i][j][l][r]+(r-l+1));
			}
		}
	}
	return ans;
}