#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 biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	int sl=0,ni=0,nj=0;
	for(int i=1;i<=N;i++)
	{
		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]==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);
	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;
}