#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9);
int biggest_stadium(int n, vector<vector<int>> f) {
vector can(n, vector(n, vector<bool>(n)));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bool ok = true;
for (int k = j; k < n; k++) {
if (!f[i][k]) {
can[i][j][k] = true;
} else {
break;
}
}
}
}
int mx = 0;
for (int pivot = 0; pivot < n; pivot++) {
vector dp(n, vector(n, vector(n, vector(n, vector<int>(2, -inf)))));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
if (i == pivot) {
if (can[i][j][k]) {
dp[i][i][j][k][0] = k - j + 1;
dp[i][i][j][k][1] = k - j + 1;
mx = max(mx, dp[i][i][j][k][0]);
}
}
}
}
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for (int k = 0; k < n; k++) {
for (int l = k; l < n; l++) {
for (int e = 0; e < n; e++) {
for (int f = e; f < n; f++) {
if (k >= e && l <= f) {
if (can[i][k][l] && can[j][e][f]) {
dp[i][j][k][l][0] = max(dp[i + 1][j][e][f][1] + (l - k + 1), dp[i][j][k][l][0]);
mx = max(mx, dp[i][j][k][l][0]);
}
if (can[i][k][l] && can[i + 1][e][f]) {
dp[i][j][k][l][0] = max(dp[i + 1][j][e][f][0] + (l - k + 1), dp[i][j][k][l][0]);
mx = max(mx, dp[i][j][k][l][0]);
}
if (can[j][k][l] && can[i][e][f]) {
dp[i][j][k][l][1] = max(dp[i][j - 1][e][f][0] + (l - k + 1), dp[i][j][k][l][1]);
mx = max(mx, dp[i][j][k][l][1]);
}
if (can[j][k][l] && can[j - 1][e][f]) {
dp[i][j][k][l][1] = max(dp[i][j - 1][e][f][1] + (l - k + 1), dp[i][j][k][l][1]);
mx = max(mx, dp[i][j][k][l][1]);
}
}
}
}
}
}
}
}
}
return mx;
}
