Submission #964432

#TimeUsernameProblemLanguageResultExecution timeMemory
964432nguyentunglamSoccer Stadium (IOI23_soccer)C++17
100 / 100
4473 ms690368 KiB
#include "soccer.h" #include<bits/stdc++.h> #define all(v) v.begin(), v.end() using namespace std; const int N = 2010; int n; bool a[N][N]; vector<int> arr[N]; int check_valid() { for(int col = 0; col < n; col++) { for(int row = 0; row < n; row++) if (a[row][col] == 0) arr[col].push_back(row); } int st = 0; while (st < n && arr[st].empty()) st++; if (st == n) return 0; int ed = st; while (ed < n && !arr[ed].empty()) ed++; ed--; for(int i = 1; i < st; i++) if (!arr[i].empty()) return 0; for(int i = ed + 1; i < n; i++) if (!arr[i].empty()) return 0; for(int i = st; i <= ed; i++) if (arr[i].size() != arr[i].back() - arr[i][0] + 1) return 0; int cnt = 0; for(int i = st; i <= ed; i++) cnt += arr[i].size(); int L = max(arr[st][0], arr[ed][0]); int R = min(arr[st].back(), arr[ed].back()); while (st <= ed) { if (arr[st].size() <= arr[ed].size()) { if (arr[st][0] <= L && arr[st].back() >= R) { L = arr[st][0]; R = arr[st].back(); st++; } else return 0; } else { if (arr[ed][0] <= L && arr[ed].back() >= R) { L = arr[ed][0]; R = arr[ed].back(); ed--; } else return 0; } } return cnt; } namespace sub4 { const int N = 51; int pref[N][N]; int dp[N][N][N][N]; int solve() { for(int i = 0; i < n; i++) { pref[i][0] = a[i][0]; for(int j = 1; j < n; j++) pref[i][j] = pref[i][j - 1] + a[i][j]; } auto check = [&] (int i, int l, int r) { int sum = pref[i][r]; if (l > 0) sum -= pref[i][l - 1]; return sum == 0; }; int ans = 0; // cout << check(1, 1, 2) << endl; memset(dp, -61, sizeof(dp)); for(int i = 0; i < n; i++) { for(int u = 0; u < n; u++) for(int v = u; v < n; v++) if (check(i, u, v)) dp[i][i][u][v] = v - u + 1; } for(int x = n - 1; x >= 0; x--) for(int y = x; y <= n; y++) { for(int u = 0; u < n; u++) for(int v = u; v < n; v++) { for(int _u = 0; _u <= u; _u++) for(int _v = v; _v < n; _v++) { if (y + 1 < n && check(y + 1, u, v)) dp[x][y + 1][u][v] = max(dp[x][y + 1][u][v], dp[x][y][_u][_v] + v - u + 1); if (x > 0 && check(x - 1, u, v)) dp[x - 1][y][u][v] = max(dp[x - 1][y][u][v], dp[x][y][_u][_v] + v - u + 1); } ans = max(ans, dp[x][y][u][v]); } } return ans; } } namespace AC { const int N = 2010, M = 2e3 * 2e3 * 2 + 10; int b[N], L[N], R[N], dp[M], trans[2][M]; int close[2][N][N]; vector<int> open[2][N][N], lst[N]; tuple<int, int, int, int> rect[M]; int solve() { // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) cout << a[i][j] << " "; cout << endl; // } int m = 0; auto histogram = [&] () { stack<int> st; for(int i = 1; i <= n; i++) { while (!st.empty() && b[st.top()] >= b[i]) st.pop(); L[i] = st.empty() ? 0 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for(int i = n; i >= 1; i--) { while (!st.empty() && b[st.top()] >= b[i]) st.pop(); R[i] = st.empty() ? n + 1 : st.top(); st.push(i); } }; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if (a[i][j]) b[j] = 0; else b[j]++; } histogram(); for(int j = 1; j <= n; j++) if (b[j]) { rect[++m] = make_tuple(i - b[j] + 1, i, L[j] + 1, R[j] - 1); } } for(int j = 1; j <= n; j++) b[j] = 0; for(int i = n; i >= 1; i--) { for(int j = 1; j <= n; j++) { if (a[i][j]) b[j] = 0; else b[j]++; } histogram(); for(int j = 1; j <= n; j++) if (b[j]) { rect[++m] = make_tuple(i, i + b[j] - 1, L[j] + 1, R[j] - 1); } } for(int i = 1; i <= m; i++) { lst[get<1> (rect[i]) - get<0> (rect[i])].push_back(i); } for(int delta = 0; delta < n; delta++) { for(int &i : lst[delta]) { int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i]; open[0][x2][y1].emplace_back(i); close[0][x2][y2]++; open[1][x1][y1].emplace_back(i); close[1][x1][y2]++; } } for(int i = 1; i <= n; i++) for(int t = 0; t < 2; t++) { stack<int> st; for(int j = 1; j <= n; j++) { for(auto &k : open[t][i][j]) { trans[t][k] = st.empty() ? 0 : st.top(); st.push(k); } while (close[t][i][j]--) st.pop(); } } int ans = 0; for(int delta = 0; delta < n; delta++) { for(int &i : lst[delta]) { int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i]; dp[i] = (x2 - x1 + 1) * (y2 - y1 + 1); if (trans[0][i]) { // top int j = trans[0][i]; dp[i] = max(dp[i], dp[j] + (get<0> (rect[j]) - x1) * (y2 - y1 + 1)); } // bottom if (trans[1][i]) { int j = trans[1][i]; dp[i] = max(dp[i], dp[j] + (x2 - get<1> (rect[j])) * (y2 - y1 + 1)); } ans = max(ans, dp[i]); } } cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl; return ans; } } int biggest_stadium(int N, std::vector<std::vector<int>> F) { n = N; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) a[i][j] = F[i][j]; // if (n <= 30) return sub4::solve(); // if (n <= 500) return sub5::solve(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = F[i - 1][j - 1]; return AC::solve(); } #ifdef ngu int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); int N; assert(1 == scanf("%d", &N)); std::vector<std::vector<int>> F(N, std::vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { assert(1 == scanf("%d", &F[i][j])); } } fclose(stdin); int res = biggest_stadium(N, F); printf("%d\n", res); fclose(stdout); return 0; } #endif // ngu

Compilation message (stderr)

soccer.cpp: In function 'int check_valid()':
soccer.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   24 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |   ^~~~~
soccer.cpp:24:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   24 |   while (ed < n && !arr[ed].empty()) ed++; ed--;
      |                                            ^~
soccer.cpp:27:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   27 |   for(int i = st; i <= ed; i++) if (arr[i].size() != arr[i].back() - arr[i][0] + 1) return 0;
      |                                     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...