#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=0;
	if (x+1<=n) res=max(res,calc(x+1,y)+r[x][y]-l[x][y]+1);
	if (fa[x][y]) res=max(res,calc(x,fa[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=1;j<=n;++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[i][dque[top]]>=R[i][j]) 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)
			if (r[i][j]!=j-1)
				ans=max(ans,calc(i,j));
	return ans;
}