#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
long long total_empty = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0) total_empty++;
}
}
// 特判全空或全满的情况
if (total_empty == N * N) return N * N;
if (total_empty == 0) return 0;
// 预处理每一行每个位置向左和向右最近的树的位置
vector<vector<int>> prev_tree(N, vector<int>(N, -1));
vector<vector<int>> next_tree(N, vector<int>(N, N));
for (int r = 0; r < N; ++r) {
int last_tree = -1;
for (int c = 0; c < N; ++c) {
if (F[r][c] == 1) last_tree = c;
prev_tree[r][c] = last_tree;
}
last_tree = N;
for (int c = N - 1; c >= 0; --c) {
if (F[r][c] == 1) last_tree = c;
next_tree[r][c] = last_tree;
}
}
vector<unordered_map<int, int>> memo_up(N);
vector<unordered_map<int, int>> memo_down(N);
// 向上扩展的 DFS 递归加记忆化
auto get_up = [&](auto& self, int M, int L, int R) -> int {
if (M < 0 || L > R) return 0;
int state = (L << 12) | R;
if (memo_up[M].count(state)) return memo_up[M][state];
int p_tree = prev_tree[M][R];
int n_tree = next_tree[M][L];
// 若当前区间内没有遇到树，直接继承范围
if (p_tree < L && n_tree > R) {
return memo_up[M][state] = (R - L + 1) + self(self, M - 1, L, R);
}
// 遇到树时，尝试所有被割裂的合法连通子空隙
int mx = 0;
int curr_l = L;
while (curr_l <= R) {
int t = next_tree[M][curr_l];
int curr_r = min(R, t - 1);
if (curr_l <= curr_r) {
mx = max(mx, (curr_r - curr_l + 1) + self(self, M - 1, curr_l, curr_r));
}
curr_l = t + 1;
}
return memo_up[M][state] = mx;
};
// 向下扩展的 DFS 递归加记忆化
auto get_down = [&](auto& self, int M, int L, int R) -> int {
if (M >= N || L > R) return 0;
int state = (L << 12) | R;
if (memo_down[M].count(state)) return memo_down[M][state];
int p_tree = prev_tree[M][R];
int n_tree = next_tree[M][L];
if (p_tree < L && n_tree > R) {
return memo_down[M][state] = (R - L + 1) + self(self, M + 1, L, R);
}
int mx = 0;
int curr_l = L;
while (curr_l <= R) {
int t = next_tree[M][curr_l];
int curr_r = min(R, t - 1);
if (curr_l <= curr_r) {
mx = max(mx, (curr_r - curr_l + 1) + self(self, M + 1, curr_l, curr_r));
}
curr_l = t + 1;
}
return memo_down[M][state] = mx;
};
int max_area = 0;
// 枚举全部可能的“骨架极大线段核心”，分别向上和向下探寻其衍生极值
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0 && (j == 0 || F[i][j - 1] == 1)) {
int end_j = j;
while (end_j + 1 < N && F[i][end_j + 1] == 0) end_j++;
int L = j, R = end_j;
int area = (R - L + 1);
area += get_up(get_up, i - 1, L, R);
area += get_down(get_down, i + 1, L, R);
if (area > max_area) {
max_area = area;
}
j = end_j;
}
}
}
return max_area;
}
