#include "soccer.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
int stadium(int N, std::vector<std::vector<int>> F) {
int n = N;
auto check = [&] (int n, vector<vector<int>> f) -> bool {
vector<pair<int, int>> seg;
for (int i=0; i<n; i++) {
int l = n, r = -1;
for (int j=0; j<n; j++) if (f[i][j] == 0) r = j;
for (int j=n-1; j>=0; j--) if (f[i][j] == 0) l = j;
for (int j=l; j<=r; j++) if (f[i][j] == 1) return false;
seg.push_back({l, r});
}
sort(seg.begin(), seg.end(), [] (pii a, pii b) {
if (a.ff != b.ff) return a.ff < b.ff;
return a.ss > b.ss;
});
int pl = -1, pr = n;
for (auto [l, r]: seg) {
if (pl <= l && r <= pr) {
pl = l, pr = r;
}else{
return false;
}
}
return true;
};
int cnt = 0;
vector<vector<int>> G(n, vector<int>(n));
for (int i=0; i<n; i++) for (int j=0; j<n; j++) G[j][i] = F[i][j];
for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (F[i][j] == 0) cnt++;
if (check(n, F) && check(n, G)) {
return cnt;
}else{
return 0;
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
int n = N;
int f = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
int k = i*n + j;
f += (F[i][j]<<k);
}
}
int ans = 0;
for (int m=0; m<(1<<(n*n))-1; m++) {
if ((m & f) != f) continue;
vector<vector<int>> R(n, vector<int>(n));
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
int k = i*n + j;
R[i][j] = (f >> k) & 1;
}
}
ans = max(ans, stadium(n, R));
}
return ans;
}
