#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int biggest_stadium(int n, vector<vector<int>> F) {
vector<vector<int>> left(n, vector<int>(n, 0));
vector<vector<int>> right(n, vector<int>(n, 0));
vector<vector<int>> up(n, vector<int>(n, 0));
vector<vector<int>> down(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (F[i][j] == 1) {
left[i][j] = 0;
} else {
if (j == 0) {
left[i][j] = 1;
} else {
left[i][j] = left[i][j-1] + 1;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = n-1; j >= 0; j--) {
if (F[i][j] == 1) {
right[i][j] = 0;
} else {
if (j == n-1) {
right[i][j] = 1;
} else {
right[i][j] = right[i][j+1] + 1;
}
}
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (F[i][j] == 1) {
up[i][j] = 0;
} else {
if (i == 0) {
up[i][j] = 1;
} else {
up[i][j] = up[i-1][j] + 1;
}
}
}
}
for (int j = 0; j < n; j++) {
for (int i = n-1; i >= 0; i--) {
if (F[i][j] == 1) {
down[i][j] = 0;
} else {
if (i == n-1) {
down[i][j] = 1;
} else {
down[i][j] = down[i+1][j] + 1;
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (F[i][j] == 0) {
int horizontal_arm = left[i][j] + right[i][j] - 1;
int vertical_arm = up[i][j] + down[i][j] - 1;
int cross = horizontal_arm + vertical_arm - 1;
ans = max(ans, cross);
}
}
}
vector<vector<int>> H(n, vector<int>(n, 0));
for (int j = 0; j < n; j++) {
if (F[0][j] == 0) {
H[0][j] = 1;
} else {
H[0][j] = 0;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
if (F[i][j] == 1) {
H[i][j] = 0;
} else {
H[i][j] = H[i-1][j] + 1;
}
}
}
for (int i = 0; i < n; i++) {
stack<int> st;
vector<int> left_index(n, 0);
for (int j = 0; j < n; j++) {
while (!st.empty() && H[i][st.top()] >= H[i][j]) {
st.pop();
}
if (st.empty()) {
left_index[j] = 0;
} else {
left_index[j] = st.top() + 1;
}
st.push(j);
}
while (!st.empty()) st.pop();
vector<int> right_index(n, 0);
for (int j = n-1; j >= 0; j--) {
while (!st.empty() && H[i][st.top()] >= H[i][j]) {
st.pop();
}
if (st.empty()) {
right_index[j] = n-1;
} else {
right_index[j] = st.top() - 1;
}
st.push(j);
}
for (int j = 0; j < n; j++) {
int width = right_index[j] - left_index[j] + 1;
int area = H[i][j] * width;
ans = max(ans, area);
}
}
return ans;
}
