#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;
// 预处理每一行每个位置向左和向右最近的树的位置
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;
}
}
// 1. O(N^3) 枚举以每个点为顶峰核心的菱形/十字形最大的包含区域
// 配合提前 break 剪枝，在非极端情况下退化到 O(N^2) 级别
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 1) continue;
int area = 0;
// 向上扩展
int left = 0, right = N - 1;
for (int r = i; r >= 0; --r) {
left = max(left, prev_tree[r][j] + 1);
right = min(right, next_tree[r][j] - 1);
if (left > right) break;
area += (right - left + 1);
}
// 向下扩展 (注意 i 已经在上方计算过，这里从 i+1 开始)
left = 0, right = N - 1;
for (int r = i + 1; r < N; ++r) {
left = max(left, prev_tree[r][j] + 1);
right = min(right, next_tree[r][j] - 1);
if (left > right) break;
area += (right - left + 1);
}
if (area > max_area) {
max_area = area;
}
}
}
// 2. 利用单调栈 O(N^2) 求出最大的纯矩形作为兜底
// 由于完全嵌套也是一种纯粹的矩形特例，这弥补了矩形偏置的极端情况
vector<vector<int>> up(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;
}
}
for (int i = 0; i < N; ++i) {
vector<int> left_bound(N, 0), right_bound(N, N - 1);
vector<int> st;
for (int j = 0; j < N; ++j) {
while (!st.empty() && up[i][st.back()] >= up[i][j]) {
st.pop_back();
}
left_bound[j] = st.empty() ? 0 : st.back() + 1;
st.push_back(j);
}
st.clear();
for (int j = N - 1; j >= 0; --j) {
while (!st.empty() && up[i][st.back()] >= up[i][j]) {
st.pop_back();
}
right_bound[j] = st.empty() ? N - 1 : st.back() - 1;
st.push_back(j);
}
for (int j = 0; j < N; ++j) {
if (up[i][j] > 0) {
int area = up[i][j] * (right_bound[j] - left_bound[j] + 1);
if (area > max_area) {
max_area = area;
}
}
}
}
return max_area;
}
