| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1360999 | 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>
#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;
vector<vector<int>> L_row(N, vector<int>(N, 0));
vector<vector<int>> R_row(N, vector<int>(N, 0));
// 预处理每一行对于每个格子，其所在连续0向左和向右遇到的第一棵树(或边界外)的坐标
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;
L_row[r][c] = last_tree + 1;
}
last_tree = N;
for (int c = N - 1; c >= 0; --c) {
if (F[r][c] == 1) last_tree = c;
R_row[r][c] = last_tree - 1;
}
}
int ans = 0;
// 为了降低时间复杂度并彻底规避包含错位
// 定义 f[u][d] 为行跨度为 u 到 d 时，能包覆出的最大面积合规十字架
// 我们将维度转置至通过不断滚动 d 以及一维列状态的交集来 O(N^2) 收敛求解
vector<int> prev_dp(N, 0);
vector<int> current_dp(N, 0);
for (int u = N - 1; u >= 0; --u) {
vector<int> L(N), R(N);
for (int c = 0; c < N; ++c) {
L[c] = L_row[u][c];
R[c] = R_row[u][c];
int width = R[c] - L[c] + 1;
prev_dp[c] = width > 0 ? width : 0;
}
for (int d = u + 1; d < N; ++d) {
const int* l_ptr = L_row[d].data();
const int* r_ptr = R_row[d].data();
// 无依赖的内存连续快速刷新，允许编译器实施矢量化扩展
#pragma GCC ivdep
for (int c = 0; c < N; ++c) {
int lv = L[c];
int ln = l_ptr[c];
L[c] = lv > ln ? lv : ln;
int rv = R[c];
int rn = r_ptr[c];
R[c] = rv < rn ? rv : rn;
int w = R[c] - L[c] + 1;
w = w > 0 ? w : 0;
// 状态机演化：交集宽度 w 叠加本段旧态(包含更小的行覆盖) 以及上一行推演过来的累积态
int v1 = current_dp[c];
int v2 = prev_dp[c];
int max_sub = v1 > v2 ? v1 : v2;
current_dp[c] = w + max_sub;
}
// 滚动下落继承
for (int c = 0; c < N; ++c) {
prev_dp[c] = current_dp[c];
}
}
// 提取每轮触达下边界 N-1 时的极值，因为所有的面积峰值在此会被最终气泡汇聚推出
for (int c = 0; c < N; ++c) {
if (prev_dp[c] > ans) {
ans = prev_dp[c];
}
}
// 清理当前状态用于下一次上界紧缩
fill(current_dp.begin(), current_dp.end(), 0);
}
return ans;
}