#include "soccer.h"
#include <bits/stdc++.h>
int dp[509][509][509],l[2009],r[2009],dp2[509][509][509],la[2009][2009];
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	memset(dp,-0x3f,sizeof(dp));
	int cq=0,x,y;
	for(int i=1;i<=N;i++) {
		int ll=N+1;
		for(int j=N;j>=1;j--) {
			if(F[i-1][j-1]) ll=j;
			if(F[i-1][j-1]) {
				cq++;x=i;y=j;
			}
			la[i][j]=ll;
		}
	}
	if(cq==1) {
		return N*N-std::min(x,N-x+1)*std::min(y,N-y+1);
	}
	if(N>500) {
		for(int i=1;i<=N;i++) {
			std::vector<int> vq;
			for(int j=1;j<=N;j++) {
				if(!F[i-1][j-1]) {
					vq.push_back(j);
				}
			}
			for(int j=1;j<vq.size();j++) {
				if(vq[j]!=vq[j-1]+1) return 0;
			}
			if(vq.empty()) l[i]=0,r[i]=0;
			else l[i]=vq[0],r[i]=vq[vq.size()-1];
		}
		int cqq=0;
		for(int i=1;i<N;i++) {
			if(l[i]>l[i+1]) {
				cqq=1;
			}
			if(l[i]<l[i+1]&&cqq==1) return 0;
		}
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(l[i]==0||l[j]==0) continue;
				if(l[i]<l[j]&&r[i]<r[j]) return 0;
				if(l[i]>l[j]&&r[i]>r[j]) return 0;
			}
		}
		return cq;
	}
	for(int i=1;i<=N;i++) {
		for(int j=1;j<=N;j++) {
			if(F[i-1][j-1]) continue;
			dp[i][i][j]=la[i][j]-1;
			dp2[i][i][j]=la[i][j]-j;
		}
	}
	int as=0;
	for(int l=1;l<=N;l++) {
		for(int i=1;i+l-1<=N;i++) {
			int j=i+l-1;
			for(int k=1;k<=N;k++) {
				as=std::max(as,dp2[i][j][k]);
				if(k>1&&dp[i][j][k]==dp[i][j][k-1]) continue;
				if(dp2[i][j][k]<0) continue;
				int x=dp[i][j][k];
				for(int l=k;l<=x;l++) {
					int z1=0,z2=0;
					if(i!=1&&F[i-2][l-1]==0) {
						dp[i-1][j][l]=std::max(dp[i-1][j][l],std::min(x,la[i-1][l]-1));
						dp2[i-1][j][l]=std::max(dp2[i-1][j][l],dp2[i][j][k]+std::min(x,la[i-1][l]-1)-l+1);
					}
					if(j!=N&&F[j][l-1]==0) {
						dp[i][j+1][l]=std::max(dp[i][j+1][l],std::min(x,la[j+1][l]-1));
						dp2[i][j+1][l]=std::max(dp2[i][j+1][l],dp2[i][j][k]+std::min(x,la[j+1][l]-1)-l+1);
					}
				}
			}
		}
	}
    return as;
}