| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1360994 | tickcrossy | Soccer Stadium (IOI23_soccer) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;
// L_row 和 R_row 预处理每一行每个位置其左右最近的边界(或树)的索引限制
vector<vector<int>> L_row(N, vector<int>(N, 0));
vector<vector<int>> R_row(N, vector<int>(N, 0));
for (int r = 0; r < N; ++r) {
int last = 0;
for (int c = 0; c < N; ++c) {
if (F[r][c] == 1) last = c + 1;
L_row[r][c] = last;
}
last = N - 1;
for (int c = N - 1; c >= 0; --c) {
if (F[r][c] == 1) last = c - 1;
R_row[r][c] = last;
}
}
// dp[d][c] 滚动复用记录处理进度：代表在区间 [u, d] 以 c 为核心列的最大可用面积
vector<vector<int>> dp(N, vector<int>(N, 0));
vector<int> L(N), R(N);
// 外层逆向枚举上边界 u
for (int u = N - 1; u >= 0; --u) {
// 初始情况：区间仅包含单独的一行 u (即 d = u)
for (int c = 0; c < N; ++c) {
L[c] = L_row[u][c];
R[c] = R_row[u][c];
int w = R[c] - L[c] + 1;
dp[u][c] = w > 0 ? w : 0;
}
// 内层顺向枚举下边界 d
for (int d = u + 1; d < N; ++d) {
const int* l_ptr = L_row[d].data();
const int* r_ptr = R_row[d].data();
int* dp_d = dp[d].data();
const int* dp_prev = dp[d-1].data();
// SIMD 极速无分支纯线性扫描
#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]
}
}
}
// 整个矩阵收缩完成，区间 [0, N-1] 会将任意 c 维度的峰值冒泡传递到全局顶层
int ans = 0;
for (int c = 0; c < N; ++c) {
if (dp[N - 1][c] > ans) {
ans = dp[N - 1][c];
}
}
return ans;
}