#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;

int n;

int mp[2010][2010];

int rd[2010];

struct RRR{
	int l,r,u,d;
	int fa,id;
}rec[4000010];
int ridx;
int pos[4000010];
int f[4000010];

bool operator < (RRR a,RRR b){
	if((a.r-a.l)!=(b.r-b.l)) return (a.r-a.l)>(b.r-b.l);
	if(a.l!=b.l) return a.l<b.l;
	if(a.r!=b.r) return a.r<b.r;
	//assert(a.u!=b.u);
	return a.u<b.u;
}

int stk[2010],tp,rid[2010];

int biggest_stadium(int N, std::vector<std::vector<int> > F){
	n=N;
	memset(mp,0x3f,sizeof(mp));
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			mp[i+1][j+1]=F[i][j];
		}
	}
	for(int col=1;col<=n;++col){
		tp=1;
		stk[tp]=0;
		for(int i=1;i<=n+1;++i){
			if((--rd[i])==-1){
				rd[i]=0;
				while(mp[i][col+rd[i]]==0) ++rd[i];
			}
			int lid=0;
			while(rd[stk[tp]]>rd[i]){
				int cid=rid[tp];
				--tp;
				lid=cid;
				rec[cid].l=col;
				rec[cid].r=col+rd[stk[tp+1]]-1;
				rec[cid].u=stk[tp]+1;
				rec[cid].d=i-1;
			}
			if(rd[stk[tp]]==rd[i]){
				stk[tp]=i;
			}
			else{
				++ridx;
				rec[ridx].id=ridx;
				rec[ridx].fa=rid[tp];
				stk[++tp]=i;
				rid[tp]=ridx;
				if(lid) rec[lid].fa=ridx;
			}
		}
	}
	sort(rec+1,rec+1+ridx);
	for(int i=1;i<=ridx;++i){
		pos[rec[i].id]=i;
	}
	int ans=0;
	for(int i=1;i<=ridx;++i){
		//cout<<rec[i].id<<' '<<rec[i].l<<' '<<rec[i].r<<' '<<rec[i].u<<' '<<rec[i].d<<' '<<rec[i].fa<<endl;
		f[i]=max(f[i],(rec[i].r-rec[i].l+1)*(rec[i].d-rec[i].u+1));
		//move right
		if(rec[i].l<rec[i].r){
			RRR tmp;
			tmp=rec[i];
			tmp.l++;
			tmp.u++;
			int nxt=lower_bound(rec+1,rec+1+ridx,tmp)-rec-1;
			int del=(rec[i].r-rec[i].l)*(rec[i].u-rec[nxt].u+rec[nxt].d-rec[i].d);
			f[nxt]=max(f[nxt],f[i]+del);
		}
		//move left
		if(rec[i].fa){
			int nxt=pos[rec[i].fa];
			int del=(rec[nxt].r-rec[nxt].l+1)*(rec[i].u-rec[nxt].u+rec[nxt].d-rec[i].d);
			f[nxt]=max(f[nxt],f[i]+del);
		}
		ans=max(ans,f[i]);
	}
	return ans;
}