#include "soccer.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using u64=unsigned long long;
using lf=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define ct const
#define il inline
#define pb push_back
#define fi first
#define se second
template<class T>
il void tomn(T&x,T ct&y){y<x?x=y,0:0;}
template<class T>
il void tomx(T&x,T ct&y){y>x?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const lf EPS=1e-10L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
//const ll INF=4e18L;
ct int INF=1.02e9;
namespace SOL{
	ct int N=2050;
	int n,a[N][N];
	namespace S0{
		bool ck(){
			int cnt=0;
			F(i,0,n-1)F(j,0,n-1)cnt+=a[i][j];
			return cnt<=1;
		}
		int main(){
			F(i,0,n-1)F(j,0,n-1)if(a[i][j]){
				return n*n-min(i+1,n-i)*min(j+1,n-j);
			}return n*n;
		}
	}
	namespace S1{
		ct int N=30;
		int f[N][N][N][N],ans;
		int main(){
			F(i,0,N-1)F(j,0,N-1)F(k,0,N-1)F(l,0,N-1)
				f[i][j][k][l]=-INF;
			G(l,n-1,0)F(r,l,n-1)F(i,0,n-1)G(j,n-1,0){
				bool flag1=1,flag2=1;
				F(k,i,j){
					flag1&=(a[l][k]==0);
					flag2&=(a[r][k]==0);
				}
				int&res=f[l][r][i][j];
				if(l==r){
					if(flag1)res=j-i+1;
					continue;
				}
				if(flag1){
					F(x,0,i)F(y,j,n-1)tomx(res,
						f[l+1][r][x][y]+(j-i+1));
				}
				if(flag2){
					F(x,0,i)F(y,j,n-1)tomx(res,
						f[l][r-1][x][y]+(j-i+1));
				}
			}
			F(i,0,N-1)F(j,0,N-1)F(k,0,N-1)F(l,0,N-1)
				tomx(ans,f[i][j][k][l]);
			return ans;
		}
	}
	namespace S2{
		int cnt,tot;
		struct Seg{int l,r;}sg[N];
		int main(){
#define NO return cnt-1
//			cnt=0;
			F(i,0,n-1)F(j,0,n-1)
				cnt+=(a[i][j]==0);
			F(i,0,n-1){
				int l=INF,r=-INF;
				F(j,0,n-1)if(a[i][j]==0)
					tomn(l,j),tomx(r,j);
				if(l<=r){
					F(j,l,r)if(a[i][j])
						NO;
					sg[++tot]=Seg{l,r};
				}
			}
			F(i,0,n-1){
				int l=INF,r=-INF;
				F(j,0,n-1)if(a[j][i]==0)
					tomn(l,j),tomx(r,j);
				if(l<=r){
					F(j,l,r)if(a[j][i])
						NO;
				}
			}
			sort(sg+1,sg+tot+1,[&](Seg x,Seg y){return x.r-x.l+1>y.r-y.l+1;});
			F(i,1,tot-1){
				Seg x=sg[i],y=sg[i+1];
				if(!(x.l<=y.l&&x.r>=y.r))
					NO;
			}
			return cnt;
		}
	}
	int main(){
		if(S0::ck())return S0::main();
		if(n<=30)return S1::main();
		return S2::main();
	}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
	SOL::n=N;
	F(i,0,N-1)F(j,0,N-1)SOL::a[i][j]=F[i][j];
    return SOL::main();
}