#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<int>> F;
int N;
int dp[31][31][31][31][31];
vector<vector<array<int, 2>>> spans(31);
int get_cnt(int i, int lj, int rj) {
int res = 0;
for (int j = lj; j <= rj; ++j) {
res += (F[i][j] == 0);
}
return res;
}
bool intersects(array<int, 2> A, array<int, 2> B) {
return (A[0] <= B[0] && B[0] <= A[1]) || (B[0] <= A[0] && A[0] <= B[1]);
}
int solve(int li, int ri, int leftbound, int rightbound, int nowi) {
// cerr << li << " " << ri << " " << leftbound << " " << rightbound << " " << nowi << "\n";
if (li < 0) return 0;
if (ri >= N) return 0;
if (dp[li][ri][leftbound][rightbound][nowi] != -1) return dp[li][ri][leftbound][rightbound][nowi];
int cnt = get_cnt(nowi, leftbound, rightbound);
// cerr << "i = " << nowi << ", j = [" << leftbound << ", " << rightbound << "] = " << cnt << "\n";
int addu = 0, addd = 0;
if (li - 1 >= 0) {
for (auto B : spans[li - 1]) {
if (intersects({leftbound, rightbound}, B)) {
addu = max(addu, solve(li - 1, ri, max(leftbound, B[0]), min(rightbound, B[1]), li - 1));
}
}
}
if (ri + 1 < N) {
for (auto B : spans[ri + 1]) {
if (intersects({leftbound, rightbound}, B)) {
addd = max(addd, solve(li, ri + 1, max(leftbound, B[0]), min(rightbound, B[1]), ri + 1));
}
}
}
// cerr << "We got that = " << li << " , " << ri << " , with " << leftbound << " " << rightbound << " = " << addd << " , " << addu << " , " << cnt << "\n";
return dp[li][ri][leftbound][rightbound][nowi] = cnt + max(addd, addu);
}
int biggest_stadium(int _N, std::vector<std::vector<int>> _F)
{
N = _N;
F = _F;
int res = 0;
cerr << "Here!\n";
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
for (int z = 0; z < N; ++z) {
for (int l = 0; l < N; ++l) {
dp[i][j][k][z][l] = -1;
}
}
}
}
}
cerr << "Starting to get spans:\n";
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N;) {
if (F[i][j] == 1) {
j++;
continue;
}
int k = j;
while (k < N && F[i][k] == 0) k += 1;
spans[i].push_back({j, k - 1});
j = k;
}
}
// cerr << "Starting to recurse:\n";
for (int i = 0; i < N; ++i) {
for (auto& [j, k] : spans[i]) {
// cerr << "Now checking i = " << i << " , lj = " << j << " , rj = " << k << "\n";
res = max(res, solve(i, i, j, k, i));
// cerr << "Done with this span\n";
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
for (int z = 0; z < N; ++z) {
// res = max(res, dp[i][j][k][z]);
}
}
}
}
return res;
}
