Submission #1040244

#TimeUsernameProblemLanguageResultExecution timeMemory
1040244erraySoccer Stadium (IOI23_soccer)C++17
14 / 100
1273 ms481448 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "/home/ioi/contests/ioi23_d2/debug.h" #else #define debug(...) void(37) #endif template<typename F> int find_last(int l, int r, F f) { while (l < r) { int mid = (l + r + 1) >> 1; if (f(mid)) { l = mid; } else { r = mid - 1; } } return l; } template<typename T> bool ckmax(T& a, T b) { if (b > a) { a = b; return true; } return false; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { vector<vector<int>> sum(N + 1, vector<int>(N + 1)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { sum[i + 1][j + 1] = F[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j]; } } vector<vector<int>> block_D(N + 1, vector<int>(N, -1)); vector<vector<int>> block_L(N, vector<int>(N, -1)), block_R(N, vector<int>(N, N)); for (int i = N - 1; i >= 0; --i) { for (int j = 0; j < N; ++j) { block_D[i][j] = block_D[i + 1][j]; if (F[i][j]) block_D[i][j] = i; } for (int j = 0; j < N; ++j) { if (j > 0) block_L[i][j] = block_L[i][j - 1]; if (F[i][j]) block_L[i][j] = j; } for (int j = N - 1; j >= 0; --j) { if (j < N - 1) block_R[i][j] = block_R[i][j + 1]; if (F[i][j]) block_R[i][j] = j; } } debug(sum, block_D, block_L, block_R); auto Rect = [&](int l, int r, int t, int b) { return (sum[b + 1][r + 1] + sum[t][l] - sum[b + 1][l] - sum[t][r + 1]); }; auto Range_col = [&](int c, int l, int r) -> array<int, 2> { int b = find_last(c, N - 1, [&](int mid) { return Rect(l, r, c, mid) == 0; }) + 1; int t = find_last(-1, c, [&](int mid) { return Rect(l, r, mid, c) != 0; }); return {t, b}; }; auto Range_row = [&](int r, int u, int d) -> array<int, 2> { int l = find_last(-1, r, [&](int mid) { return Rect(mid, r, u, d) != 0; }); int rr = find_last(r, N - 1, [&](int mid) { return Rect(r, mid, u, d) == 0; }) + 1; return {l, rr}; }; vector<vector<vector<array<int, 3>>>> to_L(N, vector<vector<array<int, 3>>>(N)), to_R(N, vector<vector<array<int, 3>>>(N)); vector<vector<array<int, 3>>> bucket(N); for (int i = N - 1; i >= 0; --i) { int last = -1; for (int j = 0; j <= N; ++j) { if (j != N && !F[i][j]) continue; int l = last + 1, r = j - 1; last = j; if (l > r) continue; debug(i, l, r); for (int ll = l; ll <= r; ++ll) { bucket[r - ll].push_back({~i, ll, r}); } for (int rr = l; rr <= r; ++rr) { bucket[rr - l].push_back({i, l, rr}); } auto[t, b] = Range_col(i, l, r); debug(t, b); if (t + 1 != i) { auto[range_l, range_r] = Range_row(l, t + 1, i - 1); int l_row = (range_l == -1 ? t + 1 : block_D[t + 1][range_l]); int r_row = (range_r == N ? t + 1 : block_D[t + 1][range_r]); debug("top", range_l, range_r, l_row, r_row); if (r < N - 1) to_L[l_row][r + 1].push_back({i, l, r}); if (l > 0) to_R[r_row][l - 1].push_back({i, l, r}); } if (i + 1 != b) { auto[range_l, range_r] = Range_row(l, i + 1, b - 1); int l_row = (range_l == -1 ? i + 1 : block_D[i + 1][range_l]); int r_row = (range_r == N ? i + 1 : block_D[i + 1][range_r]); debug("bot", range_l, range_r, l_row, r_row); if (r < N - 1) to_L[l_row][r + 1].push_back({i, l, r}); if (l > 0) to_R[r_row][l - 1].push_back({i, l, r}); } } } debug(to_L); debug(to_R); debug(bucket); vector<vector<int>> L(N, vector<int>(N)), R(N, vector<int>(N)); auto Add_L = [&](int row, int r, int val, int len) { int l = block_L[row][r]; if (l != r) ckmax(L[row][r], val - len * (r - l)); }; auto Add_R = [&](int row, int l, int val, int len) { int r = block_R[row][l]; if (l != r) ckmax(R[row][l], val - len * (r - l)); }; vector<vector<int>> len_L(N, vector<int>(N)); vector<vector<int>> len_R = len_L, mx_L = len_L, mx_R = len_L; int ans = 0;; for (int len = N - 1; len >= 0; --len) { vector<int> L_max(N), R_max(N); for (auto[row, l, r] : bucket[len]) { auto[t, b] = Range_col(row < 0 ? ~row : row, l, r);\ int len = b - t - 1; int val; int between_upd; vector<array<int, 3>> upds; if (row < 0) { row = ~row; val = R[row][l] + (r - l + 1) * len; int prev = R_max[r]; R_max[r] = val; int pos = (r + 1 == N ? row + 1 : block_D[row + 1][r + 1]); if (pos < b) { ckmax(R_max[r], prev); } if (len_R[row][r] != len) { len_R[row][r] = len; mx_R[row][r] = 0; } ckmax(mx_R[row][r], R_max[r]); between_upd = mx_R[row][r]; upds = to_R[row][l]; } else { val = L[row][r] + (r - l + 1) * len; int prev = L_max[l]; L_max[l] = val; int pos = (l - 1 == -1 ? row + 1 : block_D[row + 1][l - 1]); if (pos < b) { ckmax(L_max[l], prev); } if (len_L[row][l] != len) { len_L[row][l] = len; mx_L[row][l] = 0; } ckmax(mx_L[row][l], L_max[l]); between_upd = mx_L[row][l]; upds = to_L[row][r]; } for (auto[next_row, next_l, next_r] : upds) { Add_L(next_row, next_r, between_upd, len); Add_R(next_row, next_l, between_upd, len); } ans = max(ans, val); debug(row, l, r, t, b, val); if (t >= 0) { Add_L(t, r, val, len); Add_R(t, l, val, len); } if (b < N) { Add_L(b, r, val, len); Add_R(b, l, val, len); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...