#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int f[35][35][35][35]; 
int now[35][35];
int s[2005][2005],qzh[2005][2005];
int nl[2005],nr[2005];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	int sl=0,ni=0,nj=0;
	for(int i=1;i<=N;i++)
	{
		nl[i]=-1;
		nr[i]=-2;
		for(int j=1;j<=N;j++)
		{
			s[i][j]=F[i-1][j-1];
			qzh[i][j]=qzh[i][j-1]+s[i][j];
			sl+=s[i][j];
			if(s[i][j]==0)
			{
				if(nl[i]==-1)nl[i]=j;
				nr[i]=j;
			}
			if(s[i][j]==1)
			{
				ni=i;
				nj=j;
			}
		}
	}
	if(sl==0)return N*N;
	if(sl==1)return N*N-min(ni,N-ni+1)*min(nj,N-nj+1);
	if(N>30)
	{
		for(int i=1;i<=N;i++)if(nl[i]!=-1&&qzh[i][nr[i]]-qzh[i][nl[i]-1]!=0)return 0;
		int tl=1,tr=N,zl=0,zr=0;
		while(nl[tl]==-1)tl++;
		while(nl[tr]==-1)tr--;
		if(nr[tl]-nl[tl]+1<=nr[tr]-nl[tr]+1)
		{
			tl++;
			zl=nl[tl-1];
			zr=nr[tl-1];
		}
		else
		{
			tr--;
			zl=nl[tr+1];
			zr=nr[tr+1];
		}
		while(tl<=tr)
		{
			if(nr[tl]-nl[tl]+1<=nr[tr]-nl[tr]+1)
			{
				tl++;
				if(nl[tl-1]>zl||nr[tl-1]<zr)return 0;
				zl=nl[tl-1];
				zr=nr[tl-1];
			}
			else
			{
				tr--;
				if(nl[tr+1]>zl||nr[tr+1]<zr)return 0;
				zl=nl[tr+1];
				zr=nr[tr+1];
			}
		}
		//printf("%d %d\n",tl,tr);
		int ans=0;
		for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)if(s[i][j]==0)ans++;
		return ans;
	}
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=N-i;j++)
		{
			if(i+j==N)continue; 
			for(int k=1;k<=N;k++)
			{
				for(int l=k;l<=N;l++)
				{
					if(qzh[i+1][l]-qzh[i+1][k-1]!=0)now[k][l]=0;
					else now[k][l]=f[i][j][k][l]+l-k+1;
				}
			}
			for(int k=N;k>=1;k--)
			{
				for(int l=k;l<=N;l++)
				{
					if(k>1&&qzh[i+1][l]-qzh[i+1][k-2]==0)now[k-1][l]=max(now[k-1][l],now[k][l]+1);
					if(l<N&&qzh[i+1][l+1]-qzh[i+1][k-1]==0)now[k][l+1]=max(now[k][l+1],now[k][l]+1);
				}
			}
			for(int k=1;k<=N;k++)
			{
				for(int l=k;l<=N;l++)
				{
					f[i+1][j][k][l]=max(f[i+1][j][k][l],now[k][l]);
				}
			}
			for(int k=1;k<=N;k++)
			{
				for(int l=k;l<=N;l++)
				{
					if(qzh[N-j][l]-qzh[N-j][k-1]!=0)now[k][l]=0;
					else now[k][l]=f[i][j][k][l]+l-k+1;
				}
			}
			for(int k=N;k>=1;k--)
			{
				for(int l=k;l<=N;l++)
				{
					if(k>1&&qzh[N-j][l]-qzh[N-j][k-2]==0)now[k-1][l]=max(now[k-1][l],now[k][l]+1);
					if(l<N&&qzh[N-j][l+1]-qzh[N-j][k-1]==0)now[k][l+1]=max(now[k][l+1],now[k][l]+1);
				}
			}
			for(int k=1;k<=N;k++)
			{
				for(int l=k;l<=N;l++)
				{
					f[i][j+1][k][l]=max(f[i][j+1][k][l],now[k][l]);
				}
			}
		}
	}
	int ans=0;
	for(int k=0;k<=N;k++)
	{
		for(int l=1;l<=N;l++)
		{
			for(int r=l;r<=N;r++)
			{
				//printf("%d %d %d %d %d\n",k,N-k,l,r,f[k][N-k][l][r]);
				ans=max(ans,f[k][N-k][l][r]);
			}
		}
	}
    return ans;
}