#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
auto can = [&](int i, int j) -> bool {
return max(i, j) < N && min(i, j) >= 0 && F[i][j] == 0;
};
vector<vector<bool>> vis(N, vector<bool>(N));
int cnt = 0, res = 0;
auto dfs = [&](auto& dfs, int i, int j) -> void {
vis[i][j] = 1;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (max(ni, nj) >= N || min(ni, nj) < 0 || vis[ni][nj] || F[ni][nj] == 1) continue;
dfs(dfs, ni, nj);
}
};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!vis[i][j] && F[i][j] == 0) {
dfs(dfs, i, j);
cnt += 1;
}
res += (F[i][j] == 0);
}
}
if (cnt > 1) return 0;
vector<vector<int>> dp(N, vector<int>(N));
vector<vector<int>> left(N, vector<int>(N, -1)), right(N, vector<int>(N, -1));
vector<vector<int>> up(N, vector<int>(N, -1)), down(N, vector<int>(N, -1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dp[i][j] += F[i][j];
if (i) {
dp[i][j] += dp[i - 1][j];
}
if (j) {
dp[i][j] += dp[i][j - 1];
}
if (i && j) {
dp[i][j] -= dp[i - 1][j - 1];
}
if (F[i][j] == 0) {
left[i][j] = j;
up[i][j] = i;
}
if (j > 0) {
if (left[i][j - 1] != -1) left[i][j] = left[i][j - 1];
}
if (i > 0) {
if (up[i - 1][j] != -1) up[i][j] = up[i - 1][j];
}
}
}
for (int i = N - 1; i >= 0; --i) {
for (int j = N - 1; j >= 0; --j) {
if (F[i][j] == 0) {
right[i][j] = j;
down[i][j] = i;
}
if (j + 1 < N) {
if (right[i][j + 1] != -1) right[i][j] = right[i][j + 1];
}
if (i + 1 < N) {
if (down[i + 1][j] != -1) down[i][j] = down[i + 1][j];
}
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 1) {
if (left[i][j] != -1 && right[i][j] != -1) return 0;
if (up[i][j] != -1 && down[i][j] != -1) return 0;
}
}
}
vector<array<int, 4>> sz;
for (int i = 0; i < N; ++i) {
int now = 0;
for (int j = 0; j < N;) {
if (F[i][j] == 1) {
j++;
continue;
}
while (j < N && F[i][j] == 0) {
now += 1;
j++;
}
sz.push_back({now, j - now, j - 1, 0});
}
}
for (int j = 0; j < N; ++j) {
int now = 0;
for (int i = 0; i < N;) {
if (F[i][j] == 1) {
i++;
continue;
}
while (i < N && F[i][j] == 0) {
now += 1;
i++;
}
sz.push_back({now, i - now, i - 1, 1});
}
}
vector<bool> done(2);
sort(rbegin(sz), rend(sz));
for (auto& [a, c, d, e] : sz) {
if (done[e]) continue;
done[e] = true;
int from = c, to = d;
if (e == 1) {
for (int j = 0; j < N; ++j) {
for (int i = 0; i < from; ++i) {
if (F[i][j] == 0) return 0;
}
for (int i = to + 1; i < N; ++i) {
if (F[i][j] == 0) return 0;
}
}
} else {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < from; ++j) {
if (F[i][j] == 0) return 0;
}
for (int j = to + 1; j < N; ++j) {
if (F[i][j] == 0) return 0;
}
}
}
cerr << a << " " << c << " " << d << " " << e << "\n";
}
return res;
}
