#include "soccer.h"
#include "bits/stdc++.h"
using namespace std;
struct dsu {
vector<int> p, size;
void init(int n) {
p.assign(n + 1, 0);
size.assign(n + 1, 1);
for (int i = 1; i <= n; i++) p[i] = i;
}
int get(int a) {
return (p[a] == a ? a : p[a] = get(p[a]));
}
void add(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a, b);
size[b] += size[a];
p[a] = b;
}
};
void maxs(int &a, int b) {
if (a < b) a = b;
}
int biggest_stadium(int n, std::vector<std::vector<int>> a) {
vector<vector<pair<int, int>>> ranges(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j]) continue;
if (ranges[i].empty() or ranges[i].back().second + 1 < j) {
ranges[i].emplace_back(j, j);
} else {
ranges[i].back().second++;
}
}
}
map<tuple<int, int, bool>, int> mp;
for (int x = 0; x < n; x++) {
if (ranges[x].empty()) continue;
if (mp.empty()) {
for (auto [l, r]: ranges[x]) {
for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) {
mp[{i, j, false}] = mp[{i, j, true}] = j - i + 1;
}
}
continue;
}
map<tuple<int, int, bool>, int> nw;
for (auto [l, r]: ranges[x]) {
for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) {
nw[{i, j, false}] = nw[{i, j, true}] = j - i + 1;
int ln = j - i + 1;
for (auto [it, val]: mp) {
auto [l2, r2, tp] = it;
if (tp) {
// opening -> opening
if (i <= l2 and r2 <= j) maxs(nw[{i, j, true}], val + ln);
}
// opening/closing -> closing
if (!(l2 <= i and j <= r2)) continue;
maxs(nw[{i, j, false}], val + ln);
}
}
}
swap(nw, mp);
}
int ans = 0;
for (auto [it, val]: mp) ans = max(ans, val);
return ans;
}
