#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)))));
vector pre(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 i = 0; i < n; i++) {
for (int len = n; len >= 1; len--) {
for (int j = 0; j <= n - len; j++) {
int k = j + len - 1;
pre[i][i][j][k][0] = dp[i][i][j][k][0];
pre[i][i][j][k][1] = dp[i][i][j][k][1];
if (j - 1 >= 0) {
pre[i][i][j][k][0] = max({pre[i][i][j][k][0], dp[i][i][j][k][0], pre[i][i][j - 1][k][0]});
pre[i][i][j][k][1] = max({pre[i][i][j][k][1], dp[i][i][j][k][1], pre[i][i][j - 1][k][1]});
}
if (k + 1 < n) {
pre[i][i][j][k][0] = max({pre[i][i][j][k][0], dp[i][i][j][k][0], pre[i][i][j][k + 1][0]});
pre[i][i][j][k][1] = max({pre[i][i][j][k][1], dp[i][i][j][k][1], pre[i][i][j][k + 1][1]});
}
}
}
}
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++) {
if (can[i][k][l]) {
dp[i][j][k][l][0] = max(dp[i][j][k][l][0], pre[i + 1][j][k][l][1] + (l - k + 1));
dp[i][j][k][l][0] = max(dp[i][j][k][l][0], pre[i + 1][j][k][l][0] + (l - k + 1));
mx = max(mx, dp[i][j][k][l][0]);
}
if (can[j][k][l]) {
dp[i][j][k][l][1] = max(dp[i][j][k][l][1], pre[i][j - 1][k][l][1] + (l - k + 1));
dp[i][j][k][l][1] = max(dp[i][j][k][l][1], pre[i][j - 1][k][l][0] + (l - k + 1));
mx = max(mx, dp[i][j][k][l][1]);
}
}
}
for (int len2 = n; len2 >= 1; len2--) {
for (int k = 0; k <= n - len2; k++) {
int l = k + len2 - 1;
pre[i][j][k][l][0] = dp[i][j][k][l][0];
pre[i][j][k][l][1] = dp[i][j][k][l][1];
if (k - 1 >= 0) {
pre[i][j][k][l][0] = max({pre[i][j][k][l][0], dp[i][j][k][l][0], pre[i][j][k - 1][l][0]});
pre[i][j][k][l][1] = max({pre[i][j][k][l][1], dp[i][j][k][l][1], pre[i][j][k - 1][l][1]});
}
if (l + 1 < n) {
pre[i][j][k][l][0] = max({pre[i][j][k][l][0], dp[i][j][k][l][0], pre[i][j][k][l + 1][0]});
pre[i][j][k][l][1] = max({pre[i][j][k][l][1], dp[i][j][k][l][1], pre[i][j][k][l + 1][1]});
}
}
}
}
}
}
return mx;
}
