#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
int biggest_stadium(int n,vector<vector<int>>A){
int a[n][n+2];
for(int i=0;i<n;i++){
a[i][0]=a[i][n+1]=1;
for(int j=0;j<n;j++){
a[i][j+1]=A[i][j];
}
}
vector<pii>v[n];
for(int i=0;i<n;i++){
int last=0;
for(int j=1;j<n+2;j++){
if(a[i][j]==1){
v[i].pb({last+1,j-1});
last=j;
}
}
}
int ans=0;
for(int i=0;i<n;i++){
vector<pair<pii,int>>dp;
for(pii x:v[i]){
dp.pb({x,x.second-x.first+1});
ans=max(ans,dp.back().second);
}
for(int j=1;j<n;j++){
if(i-j<0||n<=i+j){
break;
}
vector<pair<pii,int>>newdp;
int midind=0,ind1=0,ind2=0;
while(1){
auto[x1,y1]=v[i-j][ind1];
auto[x2,y2]=v[i+j][ind2];
int intx=max(x1,x2),inty=min(y1,y2);
while(midind<dp.size()&&dp[midind].first.second<intx){
midind++;
}
for(int gy:{midind,midind+1}){
if(dp.size()<=gy)continue;
auto[x,y]=dp[gy].first;
int cost=dp[gy].second;
int X1=max(x1,x),Y1=min(y1,y);
int X2=max(x2,x),Y2=min(y2,y);
if(Y1<X1||Y2<X2)continue;
int intX=max(X1,X2),intY=min(Y1,Y2);
if(intY<intX)continue;
newdp.pb({pii{intX,intY},cost+intY-intX+1+max(Y1-X1+1,Y2-X2+1)});
ans=max(ans,newdp.back().second);
}
if(ind1+1==v[i-j].size()&&ind2+1==v[i+j].size()){
break;
}else if(ind1+1==v[i-j].size()){
ind2++;
}else if(ind2+1==v[i+j].size()){
ind1++;
}else if(v[i-j][ind1+1].first<v[i+j][ind2+1].first){
ind1++;
}else{
ind2++;
}
}
dp=newdp;
}
}
return ans;
}
