#include"soccer.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 3000
using namespace std;
const int inf=(int)(1e9);
int n,ans,R[N+1][N+1],dp[N+1][N+1],ls[N+1],rs[N+1],fa[N+1][N+1],l[N+1][N+1],r[N+1][N+1],dque[N+1],top;
bool used[N+1][N+1];
int calc(int x,int y)
{
	if (R[x][y]==y-1) return -inf;
	if (used[x][y]) return dp[x][y];
	int res=r[y][x]-l[y][x]+1;
	if (y+1<=n) res=max(res,calc(x,y+1)+r[y][x]-l[y][x]+1);
	if (fa[y][x]) res=max(res,calc(fa[y][x],y));
	used[x][y]=1,dp[x][y]=res;
	return res;
}
int biggest_stadium(int SN,vector<vector<int>>F)
{
	n=SN;
	for (int i=1;i<=n;++i) R[i][n+1]=n;
	for (int i=1;i<=n;++i)
		for (int j=n;j>=1;--j)
		{
			if (!F[i-1][j-1]) R[i][j]=R[i][j+1];
			else R[i][j]=j-1;
		}
	for (int i=1;i<=n;++i)
	{
		top=0;
		for (int j=1;j<=n;++j) ls[j]=rs[j]=0;
		for (int j=1;j<=n;++j)
		{
		    while (top&&R[dque[top]][i]>=R[j][i]) ls[j]=dque[top],top--;
			if (top) rs[dque[top]]=j;
			l[i][j]=dque[top]+1,dque[++top]=j;
		}
		for (int j=n;j>=1;--j)
		{
			if (ls[j]) fa[i][ls[j]]=j;
			if (rs[j]) fa[i][rs[j]]=j;
			if (rs[j]) r[i][j]=r[i][rs[j]];
			else r[i][j]=j;
		}
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			ans=max(ans,calc(i,j));
	return ans;
}