#include "soccer.h"
#include <bits/stdc++.h>
int dp[509][509][509],dp2[509][509][509],la[2009][2009];
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	memset(dp,-0x3f,sizeof(dp));
	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;
			la[i][j]=ll;
		}
	}
	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;
}