#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 7 + 3;
bool f[N][N];
int prefix[N][N];
int n;
pair<int, bool> dp[N][N][N][N][N][2];
void init_prefix(){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
prefix[i][j] = !f[i - 1][j - 1];
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
prefix[i][j] += prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
}
}
}
int get_sum(int x1, int y1, int x2, int y2){
if(x1 > x2 || y1 > y2)
return 0;
return prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1];
}
bool bad(int l1, int r1, int l2, int r2){
if(l1 <= l2 && r2 <= r1)
return false;
if(l2 <= l1 && r1 <= r2)
return false;
return true;
}
int solve(int l1, int r1, int l2, int r2, int i, bool up){
if(i == n)
return 0;
auto &[ans, solved] = dp[l1][r1][l2][r2][i][up];
if(solved)
return ans;
solved = true;
ans = 0;
for(int l3 = 0; l3 < n; ++l3){
for(int r3 = l3; r3 < n; ++r3){
if(f[i][r3])
break;
if(bad(l1, r1, l3, r3))
continue;
if(bad(l2, r2, l3, r3))
continue;
if(!up && (l3 < l2 || r2 < r3))
continue;
bool new_up = up;
if(up && (l2 < l3 || r3 < r2))
new_up = false;
int cand = r3 - l3 + 1;
cand += solve(l1, r1, l3, r3, i + 1, new_up);
ans = max(ans, cand);
}
}
return ans;
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F){
n = _N;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
f[i][j] = F[i][j];
init_prefix();
int ans = 0;
for(int i = 0; i < n; ++i){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
if(f[i][r])
break;
ans = max(ans, solve(l, r, l, r, i + 1, true) + r - l + 1);
}
}
}
return ans;
}
/*
3
1 0 0
0 0 0
0 0 0
*/
