#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 get(int n, vector<vector<int>> a) {
dsu ds; ds.init(n * n);
vector<tuple<int, int, int>> ranges;
for (int i = 0; i < n; i++) {
int j = 0;
while (j < n and a[i][j]) j++;
if (j == n) continue;
ranges.emplace_back(i, j, j);
while (j < n and !a[i][j]) j++;
get<2>(ranges.back()) = j - 1;
// if it contains another range?
while (j < n and a[i][j]) j++;
if (j != n) return 0;
}
// another check
// cout << ranges.size() << endl;
for (int j = 0; j < n; j++) {
int i = 0;
while (i < n and a[i][j]) i++;
if (i == n) continue;
while (i < n and !a[i][j]) i++;
while (i < n and a[i][j]) i++;
if (i != n) return 0;
}
vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
pair<int, int> any;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j]) continue;
for (int k = 0; k < 4; k++) {
auto [x, y] = make_pair(i + dx[k], j + dy[k]);
if (min(x, y) < 0 or max(x, y) >= n) continue;
if (!a[x][y]) ds.add(i * n + j, x * n + y);
}
any = make_pair(i, j);
}
}
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (!a[i][j] and ds.get(i * n + j) != ds.get(any.first * n + any.second)) {
return 0;
}
}
int sum = 0;
for (int p1 = 0; p1 < ranges.size(); p1++) {
sum += get<2>(ranges[p1]) - get<1>(ranges[p1]) + 1;
for (int p2 = 0; p2 < ranges.size(); p2++) {
auto [i, l, shit1] = ranges[p1];
auto [j, shit2, r] = ranges[p2];
bool ok = false;
ok |= !a[i][r];
ok |= !a[j][l];
if (!ok) return 0;
}
}
return sum;
}
int brute(int n, std::vector<std::vector<int>> a) {
vector<pair<int, int>> pos;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (!a[i][j]) pos.emplace_back(i, j);
}
int ln = pos.size(), ans = 0;
for (int bt = 0; bt < (1 << ln); bt++) {
auto b = a;
for (int k = 0; k < ln; k++) {
if (bt & (1 << k)) continue;
auto [i, j] = pos[k];
b[i][j] = 1;
}
ans = max(ans, get(n, b));
}
return ans;
}
bool check(int l1, int r1, int l2, int r2) {
if (l1 <= l2 and r2 <= r1) return true;
if (l2 <= l1 and r1 <= r2) return true;
return false;
}
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, int, int, bool>, int> mp;
int ans = 0;
for (int x = 0; x < n; x++) {
if (ranges[x].empty()) {
mp.clear();
continue;
}
map<tuple<int, int, 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, i, j, true}] = j - i + 1;
int ln = j - i + 1;
for (auto [it, val]: mp) {
auto [sl, sr, l2, r2, tp] = it;
if (tp) {
// opening -> opening
if (i <= l2 and r2 <= j) maxs(nw[{sl, sr, i, j, true}], val + ln);
}
// opening/closing -> closing
if (!(l2 <= i and j <= r2)) continue;
if (!check(sl, sr, i, j)) continue;
maxs(nw[{sl, sr, i, j, false}], val + ln);
}
}
}
swap(nw, mp);
for (auto [it, val]: mp) ans = max(ans, val);
// for (auto [it, val]: nw) {
// cout << get<0>(it) << ' ' << get<1>(it) << ' ' << get<2>(it) << ' ' << val << endl;
// }
// cout << endl;
}
// cout << ans << endl;
// assert(ans == brute(n, a));
return ans;
}
