#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int oo=1'000'000'000ll;
int check(int n, vector<vector<int>> F)
{
int tot=0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)tot+=F[i][j]==0;
for(int j=0;j<n;j++){ // this checks every column fulfill the condition
int stage=0;
for(int i=0;i<n;i++){
if(stage==0){
if(F[i][j]==1)continue;
else stage=1;
} else if(stage==1){
if(F[i][j]==1)stage=2;
else continue;
} else if(stage==2){
if(F[i][j]==1)continue;
else return 0;
}
}
}
for(int i=0;i<n;i++){
int stage=0;
for(int j=0;j<n;j++){
if(stage==0){
if(F[i][j]==1)continue;
else stage=1;
} else if(stage==1){
if(F[i][j]==1)stage=2;
else continue;
} else if(stage==2){
if(F[i][j]==1)continue;
else return 0;
}
}
}
vector<int> F1(n,oo);
vector<int> L0(n,-1);
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
if(F[i][j] == 0){
L0[j]=i;
} else{
F1[j]=min(F1[j],i);
}
}
}
for(int i=0;i<n;i++){
vector<int> vec;
for(int j=0;j<n;j++)if(F[i][j]==0){
vec.push_back(j);
}
if(vec.empty())continue;
int st=vec[0], en=vec.back();
int worst=oo;
for(int i=st;i<=en;i++){
worst=min(worst,L0[i]);
}
int best=0;
for(int i=0;i<st;i++){
best=max(best,L0[i]);
}
for(int i=en+1;i<n;i++){
best=max(best,L0[i]);
}
if(best>worst){
return 0;
}
}
return tot;
}
const int MAXN=31;
int dp[MAXN][MAXN][MAXN][MAXN];
int biggest_stadium(int n, vector<vector<int>> F)
{
int can=check(n,F);
int ans=0;
if(can)return can;
for(int i=0;i<MAXN;i++)for(int j=0;j<MAXN;j++)for(int k=0;k<MAXN;k++)for(int z=0;z<MAXN;z++)dp[i][j][k][z]=-oo;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=j;k<n;k++){
if(F[i][k]==1)break;
dp[i][i][j][k]=k-j+1;
ans=max(ans,k-j+1);
}
}
}
for(int i=n-1;i>=0;i--){
for(int j=i;j<=n-1;j++){
for(int x=0;x<n;x++){
for(int y=x;y<n;y++){
if(dp[i][j][x][y] == -oo)continue;//no way bro
ans=max(ans,dp[i][j][x][y]);
if(i!=0){ // try putting a thing at i-1
for(int nx=x;nx<=y;nx++){
for(int ny=nx;ny<=y;ny++){
if(F[i-1][ny] == 1)break; // cannot
dp[i-1][j][nx][ny]=max(dp[i-1][j][nx][ny],dp[i][j][x][y]+(ny-nx+1));
ans=max(ans,dp[i-1][j][nx][ny]);
}
}
}
if(j!=n-1){
for(int nx=x;nx<=y;nx++){
for(int ny=nx;ny<=y;ny++){
if(F[j+1][ny] == 1)break; // cannot
dp[i][j+1][nx][ny]=max(dp[i][j+1][nx][ny],dp[i][j][x][y]+(ny-nx+1));
ans=max(ans,dp[i][j+1][nx][ny]);
}
}
}
}
}
}
}
return ans;
}
