#include <vector>
#include <algorithm>
#include <iostream>
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;
int max_area = 0;
// up[i][j] 记录 (i, j) 及其上方连续的空单元格数
// down[i][j] 记录 (i, j) 及其下方连续的空单元格数
vector<vector<int>> up(N, vector<int>(N, 0));
vector<vector<int>> down(N, vector<int>(N, 0));
for (int j = 0; j < N; ++j) {
int cnt = 0;
for (int i = 0; i < N; ++i) {
if (F[i][j] == 0) cnt++;
else cnt = 0;
up[i][j] = cnt;
}
cnt = 0;
for (int i = N - 1; i >= 0; --i) {
if (F[i][j] == 0) cnt++;
else cnt = 0;
down[i][j] = cnt;
}
}
// 通过枚举作为“骨架”的行
for (int i = 0; i < N; ++i) {
vector<int> h(N, 0);
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0) {
h[j] = up[i][j] + down[i][j] - 1;
}
}
// 类似于最大矩形算法，利用单调栈处理当前行为基准的最大外扩
vector<int> left(N, 0), right(N, N - 1);
vector<int> st;
for (int j = 0; j < N; ++j) {
while (!st.empty() && h[st.back()] >= h[j]) {
st.pop_back();
}
left[j] = st.empty() ? 0 : st.back() + 1;
st.push_back(j);
}
st.clear();
for (int j = N - 1; j >= 0; --j) {
while (!st.empty() && h[st.back()] >= h[j]) {
st.pop_back();
}
right[j] = st.empty() ? N - 1 : st.back() - 1;
st.push_back(j);
}
for (int j = 0; j < N; ++j) {
if (h[j] > 0) {
int area = h[j] * (right[j] - left[j] + 1);
if (area > max_area) {
max_area = area;
}
}
}
}
// DP 求解最大嵌套核心面积扩展
// 我们同样需要在垂直方向跑一趟对称的逻辑并融合两者最大值，此部分为二维拓展的基座
vector<vector<int>> left_arr(N, vector<int>(N, 0));
vector<vector<int>> right_arr(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) {
int cnt = 0;
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0) cnt++;
else cnt = 0;
left_arr[i][j] = cnt;
}
cnt = 0;
for (int j = N - 1; j >= 0; --j) {
if (F[i][j] == 0) cnt++;
else cnt = 0;
right_arr[i][j] = cnt;
}
}
for (int j = 0; j < N; ++j) {
vector<int> w(N, 0);
for (int i = 0; i < N; ++i) {
if (F[i][j] == 0) {
w[i] = left_arr[i][j] + right_arr[i][j] - 1;
}
}
vector<int> up_limit(N, 0), down_limit(N, N - 1);
vector<int> st;
for (int i = 0; i < N; ++i) {
while (!st.empty() && w[st.back()] >= w[i]) st.pop_back();
up_limit[i] = st.empty() ? 0 : st.back() + 1;
st.push_back(i);
}
st.clear();
for (int i = N - 1; i >= 0; --i) {
while (!st.empty() && w[st.back()] >= w[i]) st.pop_back();
down_limit[i] = st.empty() ? N - 1 : st.back() - 1;
st.push_back(i);
}
for (int i = 0; i < N; ++i) {
if (w[i] > 0) {
int area = w[i] * (down_limit[i] - up_limit[i] + 1);
if (area > max_area) {
max_area = area;
}
}
}
}
// 返回能构造出的合法区域的最大值（子任务兼容基准）
return max_area;
}
