#include "soccer.h"
#include <bits/stdc++.h>
const int inf=1e9;
using namespace std;
int f[2010][2010],n,u[2010][2010],d[2010][2010],l[2010][2010],mn[2010][2010],mx[2010][2010];
vector<pair<int,int> >v[2010];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	n=N;
	for(int i=0;i<=n;i++) v[i].clear();
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			u[i][j]=!F[i][j]?(i?u[i-1][j]:i):i+1;
			l[i][j]=!F[i][j]?(j?l[i][j-1]:j):j+1;
			v[j-l[i][j]+1].push_back({i,j});
		}
	}
	for(int i=n-1;i>=0;i--){
		for(int j=n-1;j>=0;j--){
			d[i][j]=!F[i][j]?(i+1<n?d[i+1][j]:i):i-1;
		}
	}
	for(int i=0;i<n;i++) for(int j=1;j<n;j++) if(!F[i][j-1]){
		u[i][j]=max(u[i][j-1],u[i][j]);
		d[i][j]=min(d[i][j-1],d[i][j]);
	}
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=-inf;
	for(int _=1;_<=n;_++) for(auto __:v[_]){
		int i=__.first,j=__.second,L=d[i][j]-u[i][j]+1;
		if(L<=0) continue;
//		cerr<<_<<" "<<i<<" "<<j<<" "<<L<<"\n";
		f[i][j]=max(f[i][j],(j&&!F[i][j-1]?f[i][j-1]:0)+L);
		if(u[i][j]&&!F[u[i][j]-1][j]) f[i][j]=max(f[i][j],f[u[i][j]-1][j]+(l[u[i][j]-1][j]-l[i][j])*L);
		if(d[i][j]+1<n&&!F[d[i][j]+1][j]) f[i][j]=max(f[i][j],f[d[i][j]+1][j]+(l[d[i][j]+1][j]-l[i][j])*L);
//		printf("f[%d][%d]=%d\n",i,j,f[i][j]);
	}
	int ans=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) ans=max(ans,f[i][j]);
    return ans;
}