#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[2001][2001];
typedef pair<int,int> P;
typedef pair<P,P> PP;
map<int,int> mp[2001][2001];
int psum[2001][2001];
int ri[2001][2001];
int ntr[2001][2001];
const long long three=1e12;
const long long two=1e8;
const long long one=1e4;
int query(int u,int d,int l,int r) {
return psum[d][r]-psum[u-1][r]-psum[d][l-1]+psum[u-1][l-1];
}
long long hhash(PP x) {
return x.first.first*three+x.first.second*two+x.second.first*one+x.second.second;
}
PP unhash(long long x) {
PP ret;
ret.second.second=x%(n+1);
x/=n+1;
ret.second.first=x%(n+1);
x/=n+1;
ret.first.second=x%(n+1);
x/=n+1;
ret.first.first=x%(n+1);
return ret;
}
int ans(int l,int r,int u,int d) {
if (mp[l][r].find(u)!=mp[l][r].end()) {
return mp[l][r][u];
}
int now=l;
if (arr[u-1][now]==1) {
now=ntr[u-1][now];
}
int ret=(d-u+1)*(r-l+1);
if (u>1) {
while (now<=r) {
int ll=now;
int rr=min(ri[u-1][now],r);
int uu=u;
int dd=d;
int lo=0;
int hi=u;
int val=psum[u-1][rr]-psum[u-1][ll-1];
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (-psum[mid-1][rr]+psum[mid-1][ll-1]==-val) {
hi=mid;
}
else {
lo=mid;
}
}
uu=hi;
ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1));
now=ntr[u-1][ri[u-1][now]];
}
}
now=l;
if (arr[d+1][now]==1) {
now=ntr[d+1][now];
}
if (d<n) {
while (now<=r) {
int ll=now;
int rr=min(ri[d+1][now],r);
int uu=u;
int dd=d;
int lo=d;
int hi=n+1;
int val=-psum[d][rr]+psum[d][ll-1];
while (lo+1<hi) {
int mid=(lo+hi)/2;
if (psum[mid][rr]-psum[mid][ll-1]==-val) {
lo=mid;
}
else {
hi=mid;
}
}
dd=lo;
ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1));
now=ntr[d+1][ri[d+1][now]];
}
}
return mp[l][r][u]=ret;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
n=N;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
arr[i+1][j+1]=F[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j];
}
}
for(int i=1;i<=n;i++) {
int pr=0;
for(int j=1;j<=n;j++) {
if (arr[i][j]==1) {
for(int k=pr+1;k<j;k++) {
ri[i][k]=j-1;
}
pr=j;
}
}
for(int j=pr+1;j<=n;j++) {
ri[i][j]=n;
}
pr=1;
for(int j=1;j<=n;j++) {
if (arr[i][j]==0) {
for(int k=pr;k<j;k++) {
ntr[i][k]=j;
}
pr=j;
}
}
for(int k=pr;k<=n;k++) {
ntr[i][k]=n+1;
}
}
int ret=0;
for(int i=1;i<=n;i++) {
int pr=0;
for(int j=1;j<=n;j++) {
if (arr[i][j]==1) {
if (pr+1<=j-1) {
ret=max(ret,ans(pr+1,j-1,i,i));
}
pr=j;
}
}
if (pr!=n) {
ret=max(ret,ans(pr+1,n,i,i));
}
}
return ret;
}
