#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;}
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];
	}
	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;
}