#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<vector<int>> F;
unordered_map<ll,int> dp;
ll h(ll t, ll b, ll l, ll r){
return t*pow(2000, 3)+b*pow(2000, 2)+l*2000+r;
}
int solve(int t, int b, int l, int r){
if (l == -1) return -pow(10, 9);
if (dp.find(h(t, b, l, r)) != dp.end()) return dp[h(t, b, l, r)];
int res = 0;
if (t > 0){
int lb = -1;
for (int j=l; j<=r+1; j++){
if (j == r+1 || F[t-1][j]){
res = max(res, j-lb+solve(t-1, b, lb, j-1));
lb = -1;
}
else if (lb == -1) lb = j;
}
}
if (b < N-1){
int lb = -1;
for (int j=l; j<=r+1; j++){
if (j == r+1 || F[b+1][j]){
res = max(res, j-lb+solve(t, b+1, lb, j-1));
lb = -1;
}
else if (lb == -1) lb = j;
}
}
return dp[h(t, b, l, r)] = res;
}
int biggest_stadium(int N, vector<vector<int>> F){
::N = N;
::F = F;
int res = 0;
for (int i=0; i<N; i++){
int l = -1;
for (int j=0; j<=N; j++){
if (j == N || F[i][j]){
res = max(res, j-l+solve(i, i, l, j-1));
l = -1;
}
else if (l == -1) l = j;
}
}
return res;
}
