#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,nn,ht[2069],lg2[2069],dp[8000069],z=0;
bitset<2069> a[2069];
pair<pair<int,int>,pair<int,int>> ky[8000069];
map<pair<pair<int,int>,pair<int,int>>,int> ykmp;
pair<int,int> sp[2][2069][11][2069];
vector<pair<int,int>> al[8000069];
bitset<8000069> vtd;
inline int yk(int lb,int rb,int lb2,int rb2)
{
int k=ykmp[{{lb,rb},{lb2,rb2}}];
if(!k)
{
nn++;
ky[nn]={{lb,rb},{lb2,rb2}};
ykmp[{{lb,rb},{lb2,rb2}}]=nn;
return nn;
}
else
{
return k;
}
}
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)
{
int w,clb,crb,lb,rb,lb2,rb2;
clb=ky[x].fr.fr;
crb=ky[x].fr.sc;
lb=ky[y].fr.fr;
rb=ky[y].fr.sc;
lb2=ky[y].sc.fr;
rb2=ky[y].sc.sc;
w=(rb-lb-(crb-clb))*(rb2-lb2+1);
al[x].push_back({y,w});
}
inline int dnc(int xx,int x,int lb,int rb)
{
if(lb<=rb)
{
int u,k,l,p,p2,e,clb,crb,clb2,crb2;
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=yk(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);
if(tmp2.fr!=tmp.fr)
{
clb2=x-(tmp.fr-1)*u;
crb2=x-(tmp.fr-tmp2.fr)*u;
if(xx)
{
swap(clb2,crb2);
}
p2=yk(clb2,crb2,lb,rb);
ae(p,p2);
}
}
return p;
}
else
{
return -1;
}
}
void dfs(int x)
{
int i,sz=al[x].size(),l,w,lb,rb,lb2,rb2;
vtd[x]=1;
dp[x]=0;
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
w=al[x][i].sc;
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;
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(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<=nn;i++)
{
if(!vtd[i])
{
dfs(i);
}
}
return z;
}
