| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1360975 | 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;
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;
}
}
int max_area = 0;
vector<int> L(N), R(N);
vector<int> prev_L(N, -1), prev_R(N, -1);
vector<int> dp(N);
// 枚举以此为核心轴列构成的嵌套相连球场
for (int c = 0; c < N; ++c) {
bool same = true;
for (int i = 0; i < N; ++i) {
if (F[i][c] == 1) {
L[i] = 1;
R[i] = -1;
} else {
L[i] = prev_tree[i][c] + 1;
R[i] = next_tree[i][c] - 1;
}
if (L[i] != prev_L[i] || R[i] != prev_R[i]) {
same = false;
}
}
// 当连续空地的拓扑形貌相同时，跳过重复的多余 DP 计算
if (c > 0 && same) {
continue;
}
for(int i = 0; i < N; ++i) {
prev_L[i] = L[i];
prev_R[i] = R[i];
}
// DP: dp[d] 代表了处理中的当前上界 u 和 下界 d 时涵盖了合规列相交宽度的最大累计球场面积
for (int u = N - 1; u >= 0; --u) {
int max_l = L[u];
int min_r = R[u];
int w = min_r - max_l + 1;
if (w < 0) w = 0;
dp[u] = w;
int prev_dp = w;
for (int d = u + 1; d < N; ++d) {
if (L[d] > max_l) max_l = L[d];
if (R[d] < min_r) min_r = R[d];
w = min_r - max_l + 1;
// 【核心优化】一旦交集断开产生无效段 (w <= 0)，后续扩展无需计算相交增益
// 直接向后无脑平移最大承载值覆盖，可让极端常数骤降一个极坐标级
if (w <= 0) {
for (int d2 = d; d2 < N; ++d2) {
if (prev_dp > dp[d2]) {
dp[d2] = prev_dp;
} else {
prev_dp = dp[d2];
}
}
break;
}
int dp_d = dp[d];
int opt = (dp_d > prev_dp) ? dp_d : prev_dp;
int new_dp = w + opt;
dp[d] = new_dp;
prev_dp = new_dp;
}
}
if (dp[N - 1] > max_area) {
max_area = dp[N - 1];
}
}
return max_area;
}