#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2000
#define M 30
using namespace std;
const int inf=(int)(1e9);
struct reads
{
	int l,r;
	bool operator < (const reads &t)const
    {
		return l!=t.l?l<t.l:r>t.r;	
	}
};
reads tong[N+1];
int n,length,L[M+1],R[M+1],sl[M+1][M+1],sr[M+1][M+1],dp[M+1][M+1];
int biggest_stadium(int SN,vector<vector<int>>F)
{
	int ans=0,cnt=0,l,r,ps;
	n=SN;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			cnt+=F[i-1][j-1];
	if (!cnt) return n*n;
	if (cnt==1)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (F[i-1][j-1])
					ans=max(ans,n*n-min(i,n+1-i)*min(j,n+1-j));
		return ans;
	}
	if (n>500)
	{
		for (int i=1;i<=n;++i)
		{
			cnt=0,l=inf,r=0;
			for (int j=1;j<=n;++j)
				if (!F[i-1][j-1])
					cnt++,l=min(l,j),r=max(r,j);
			if (cnt&&r-l+1!=cnt) return 0;
			if (cnt) tong[++length]=(reads){l,r};
		}
		for (int i=1;i<=n;++i)
		{
			cnt=0,l=inf,r=0;
			for (int j=1;j<=n;++j)
				if (!F[j-1][i-1])
					cnt++,l=min(l,j),r=max(r,j);
			if (cnt&&r-l+1!=cnt) return 0;
		}
		sort(tong+1,tong+length+1);
		for (int i=1;i<=length-1;++i)
			if (tong[i].l>tong[i+1].l||tong[i].r<tong[i+1].r)
				return 0;
		cnt=0;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				cnt+=(!F[i-1][j-1]);
		return cnt;
	}
	else
	{
		for (int i=1;i<=n;++i)
		{
			for (int j=1;j<=n;++j)
			{
				if (!F[j-1][i-1])
				{
					ps=i;
					while (ps-1>=1&&!F[j-1][ps-2]) ps--;
					L[j]=ps,ps=i;
					while (ps+1<=n&&!F[j-1][ps]) ps++;
					R[j]=ps;
				}
				else L[j]=inf,R[j]=0;
			}
			for (int j=1;j<=n;++j)
				for (int k=j;k<=n;++k)
					dp[j][k]=-inf;
			for (int j=n;j>=1;--j)
				for (int k=j;k<=n;++k)
				{
					if (j==k) sl[j][k]=L[j],sr[j][k]=R[j];
					else sl[j][k]=max(sl[j][k-1],L[k]),sr[j][k]=min(sr[j][k-1],R[k]);
				}
			for (int j=1;j<=n;++j)
				if (L[j]!=inf)
					dp[j][j]=R[j]-L[j]+1,ans=max(ans,R[j]-L[j]+1);
			for (int j=n;j>=1;--j)
				for (int k=j+1;k<=n;++k)
					if (sl[j][k]<=sr[j][k])
						dp[j][k]=max(dp[j][k],max(dp[j][k-1],dp[j+1][k])+sr[j][k]-sl[j][k]+1),ans=max(ans,dp[j][k]);
		}
		return ans;
	}
}