#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,ht[2069],lg2[2069],dp[8000069],dsu[8000069],z=0;
bitset<2069> a[2069];
pair<pair<int,int>,pair<int,int>> ky[8000069];
pair<int,int> sp[2][2069][11][2069];
vector<int> al[8000069];
bitset<8000069> vtd;
inline int god(int xx,int x,int y)
{
return xx*n*n+(x-1)*n+y;
}
inline void spbd(int xx,int x)
{
int i,j;
for(i=1;i<=n;i++)
{
sp[xx][x][0][i]={ht[i],i};
}
for(i=1;1<<i<=n;i++)
{
for(j=1;j<=n-(1<<i)+1;j++)
{
sp[xx][x][i][j]=min(sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<i-1)]);
}
}
}
inline pair<int,int> spqr(int xx,int x,int lb,int rb)
{
int e=lg2[rb-lb+1];
return min(sp[xx][x][e][lb],sp[xx][x][e][rb-(1<<e)+1]);
}
inline void ae(int x,int y)
{
al[x].push_back(y);
}
int fd(int x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
inline int dnc(int xx,int x,int lb,int rb)
{
if(lb<=rb)
{
int u,k,l,p,p2,e,clb,crb;
pair<int,int> tmp=spqr(xx,x,lb,rb),tmp2;
u=!xx*2-1;
clb=x-(tmp.fr-1)*u;
crb=x;
if(xx)
{
swap(clb,crb);
}
if(clb<=crb)
{
p=god(xx,x,tmp.sc);
ky[p]={{clb,crb},{lb,rb}};
}
else
{
p=-1;
}
for(k=lb,l=rb;k<=l;k=e+1)
{
tmp2=spqr(xx,x,k,l);
if(tmp2.fr!=tmp.fr)
{
break;
}
e=tmp2.sc;
p2=dnc(xx,x,k,e-1);
if(p!=-1&&p2!=-1)
{
ae(p,p2);
}
}
p2=dnc(xx,x,k,l);
if(p!=-1&&p2!=-1)
{
ae(p,p2);
}
if(p!=-1)
{
tmp2=spqr(!xx,x-(tmp.fr-1)*u,lb,rb);
p2=god(!xx,x-(tmp.fr-1)*u,tmp2.sc);
if(tmp2.fr!=tmp.fr)
{
ae(p,p2);
}
else
{
dsu[fd(p2)]=fd(p);
}
}
return p;
}
else
{
return -1;
}
}
void dfs(int x)
{
int i,sz=al[x].size(),l,w,clb,crb,lb,rb,lb2,rb2;
vtd[x]=1;
dp[x]=0;
for(i=0;i<sz;i++)
{
l=fd(al[x][i]);
clb=ky[x].fr.fr;
crb=ky[x].fr.sc;
lb=ky[l].fr.fr;
rb=ky[l].fr.sc;
lb2=ky[l].sc.fr;
rb2=ky[l].sc.sc;
w=(rb-lb-(crb-clb))*(rb2-lb2+1);
if(!vtd[l])
{
dfs(l);
}
dp[x]=max(dp[x],dp[l]+w);
}
lb=ky[x].fr.fr;
rb=ky[x].fr.sc;
lb2=ky[x].sc.fr;
rb2=ky[x].sc.sc;
z=max(z,dp[x]+(rb-lb+1)*(rb2-lb2+1));
}
int biggest_stadium(int on,vector<vector<int>> oa)
{
int i,j,ii,u,k,l,sz;
n=on;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
a[i][j]=oa[i-1][j-1];
}
for(k=i;k>1;k/=2,lg2[i]++);
}
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
for(i=1;i<=n;i++)
{
ht[i]=0;
}
for(i=1+(n-1)*ii;i&&i<=n;i+=u)
{
for(j=1;j<=n;j++)
{
ht[j]=(ht[j]+1)*!a[i][j];
}
spbd(ii,i);
}
}
for(i=1;i<=n*n*2;i++)
{
dsu[i]=i;
}
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
for(i=1+(n-1)*ii;i&&i<=n;i+=u)
{
dnc(ii,i,1,n);
}
}
for(i=1;i<=n*n*2;i++)
{
if(fd(i)!=i)
{
sz=al[i].size();
for(j=0;j<sz;j++)
{
l=al[i][j];
al[fd(i)].push_back(l);
}
}
}
for(i=1;i<=n*n*2;i++)
{
if(ky[i].fr.fr&&!vtd[i])
{
dfs(i);
}
}
return z;
}
