#include "soccer.h"
#include <bits/stdc++.h>
int n,next[2010][2010],sum[2010][2010],ans;
std::map<std::pair<std::pair<int,int>,std::pair<int,int>>,int>val;
std::priority_queue<std::pair<int,std::pair<std::pair<int,int>,std::pair<int,int>>>>q;
int suma(int i,int ii,int j,int jj)
{
return sum[ii+1][jj+1]-sum[ii+1][j]-sum[i][jj+1]+sum[i][j];
}
void adauga(int up,int down,int l,int r,int valac)
{
int b=0,e=up-1;
while(b<=e)
{
int m=(b+e)/2;
if(suma(m,up,l,r)==0)
e=m-1;
else
b=m+1;
}
valac+=(r-l+1)*(up-b);
up=b;
b=down+1,e=n-1;
while(b<=e)
{
int m=(b+e)/2;
if(suma(down,m,l,r)==0)
b=m+1;
else
e=m-1;
}
valac+=(r-l+1)*(e-down);
down=e;
std::pair<std::pair<int,int>,std::pair<int,int>>cod={{up,down},{l,r}};
if(val.find(cod)==val.end())
{
q.push({up-down,cod});
val[cod]=valac;
}
else
if(valac>val[cod])
val[cod]=valac;
if(valac>ans)
ans=valac;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
n=N;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+F[i-1][j-1];
for(int i=0;i<n;++i)
{
next[i][n]=n-1;
for(int j=n-1;j>=0;--j)
{
if(F[i][j]==1)
next[i][j]=j-1;
else
next[i][j]=next[i][j+1];
}
}
for(int i=0;i<n;++i)
{
int poz=0;
while(poz!=n)
{
if(next[i][poz]<poz)
++poz;
else
{
adauga(i,i,poz,next[i][poz],next[i][poz]-poz+1);
poz=next[i][poz]+1;
}
}
}
while(!q.empty())
{
std::pair<std::pair<int,int>,std::pair<int,int>>cod=q.top().second;
q.pop();
int up=cod.first.first;
int down=cod.first.second;
int l=cod.second.first;
int r=cod.second.second;
if(up)
{
int poz=l;
while(poz<=r)
{
if(next[up-1][poz]>=poz)
{
adauga(up-1,down,poz,std::min(next[up-1][poz],r),val[cod]+std::min(next[up-1][poz],r)-poz+1);
poz=next[up-1][poz]+1;
}
else
++poz;
}
}
if(down+1!=n)
{
int poz=l;
while(poz<=r)
{
if(next[down+1][poz]>=poz)
{
adauga(up,down+1,poz,std::min(next[down+1][poz],r),val[cod]+std::min(next[down+1][poz],r)-poz+1);
poz=next[down+1][poz]+1;
}
else
++poz;
}
}
}
return ans;
}
