#include <vector>
#include <algorithm>
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;
// 为了最大化 CPU 缓存命中率与触发内存连续预取，全部采用 1D 拉平数组
vector<int> L_row(N * N);
vector<int> R_row(N * N);
// 预处理每行对于每个位置其左侧/右侧最近边界(或树)的索引限制
for (int r = 0; r < N; ++r) {
int last = 0;
int row_offset = r * N;
for (int c = 0; c < N; ++c) {
if (F[r][c] == 1) last = c + 1;
L_row[row_offset + c] = last;
}
last = N - 1;
for (int c = N - 1; c >= 0; --c) {
if (F[r][c] == 1) last = c - 1;
R_row[row_offset + c] = last;
}
}
// dp 数组维持二维拉平：dp[d_offset + c] 代表了处理中的当前上界 u 和 下界 d 时涵盖了合规核心列的最广面积
vector<int> dp(N * N, 0);
vector<int> L(N), R(N);
// 外层逆向枚举上边界 u
for (int u = N - 1; u >= 0; --u) {
int u_offset = u * N;
// 初始情况：区间仅包含单独的一行 u (即 d = u)
for (int c = 0; c < N; ++c) {
L[c] = L_row[u_offset + c];
R[c] = R_row[u_offset + c];
int w = R[c] - L[c] + 1;
dp[u_offset + c] = w > 0 ? w : 0;
}
// 中层顺向枚举下边界 d
for (int d = u + 1; d < N; ++d) {
int d_offset = d * N;
int prev_offset = (d - 1) * N;
const int* l_ptr = &L_row[d_offset];
const int* r_ptr = &R_row[d_offset];
int* dp_d = &dp[d_offset];
const int* dp_prev = &dp[prev_offset];
// 内层由核心列 c 担当，完全无分支 + SIMD 向量化强行提速
// 通过无脑 max(0, width) 消除了 if (w <= 0) break; 带来的流水线惩罚，完美继承断层推演
#pragma GCC ivdep
for (int c = 0; c < N; ++c) {
int l_val = L[c];
int l_new = l_ptr[c];
L[c] = l_val > l_new ? l_val : l_new;
int r_val = R[c];
int r_new = r_ptr[c];
R[c] = r_val < r_new ? r_val : r_new;
int w = R[c] - L[c] + 1;
w = w > 0 ? w : 0;
int v1 = dp_d[c]; // 来自之前的 u (即 u+1), 目前还是旧值：代表 [u+1, d]
int v2 = dp_prev[c]; // 刚刚处理过的本次的 u，d-1 的新值：代表 [u, d-1]
int mx = v1 > v2 ? v1 : v2;
dp_d[c] = w + mx; // 原地覆盖更新为全新的 [u, d]
}
}
}
// 整个矩阵收缩归纳完成，对于任意核心列 c 峰值都最终浮现于顶层 [0, N-1] 区间之中
int ans = 0;
int last_offset = (N - 1) * N;
for (int c = 0; c < N; ++c) {
if (dp[last_offset + c] > ans) {
ans = dp[last_offset + c];
}
}
return ans;
}
