Submission #1017141

#TimeUsernameProblemLanguageResultExecution timeMemory
1017141MilosMilutinovicSoccer Stadium (IOI23_soccer)C++17
100 / 100
4258 ms767284 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; const int MAX = 2005; const int LOG = 12; int n, a[MAX][MAX]; int L[MAX][MAX]; int R[MAX][MAX]; int U[MAX][MAX]; int D[MAX][MAX]; int go[MAX][MAX]; int sum[MAX][MAX]; int logs[MAX]; int st_U[LOG][MAX][MAX]; int st_D[LOG][MAX][MAX]; int res; map<pair<int, int>, int> mp[MAX][MAX]; int query_U(int i, int l, int r) { int k = logs[r - l + 1]; return max(st_U[k][i][l], st_U[k][i][r - (1 << k) + 1]); } int query_D(int i, int l, int r) { int k = logs[r - l + 1]; return min(st_D[k][i][l], st_D[k][i][r - (1 << k) + 1]); } int get_sum(int i, int l, int r) { return sum[i][r] - (l == 0 ? 0 : sum[i][l - 1]); } void rec(int xl, int xr, int yl, int yr, int cur) { if (mp[xl][xr][{yl, yr}] >= cur) { return; } res = max(res, cur); mp[xl][xr][{yl, yr}] = cur; //vector<array<int, 5>> to; if (xl > 0) { // up int ptr = yl; while (ptr <= yr) { if (a[xl - 1][ptr] == 1) { ptr = go[xl - 1][ptr]; continue; } int t = min(yr, R[xl - 1][ptr]); int new_xl = query_U(xl - 1, ptr, t); int new_xr = ((xr == n - 1 || get_sum(xr + 1, ptr, t) > 0) ? xr : query_D(xr + 1, ptr, t)); //to.push_back({cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr), new_xl, new_xr, ptr, t}); rec(new_xl, new_xr, ptr, t, cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr)); ptr = R[xl - 1][ptr] + 1; } } if (xr + 1 < n) { // down int ptr = yl; while (ptr <= yr) { if (a[xr + 1][ptr] == 1) { ptr = go[xr + 1][ptr]; continue; } int t = min(yr, R[xr + 1][ptr]); int new_xr = query_D(xr + 1, ptr, t); int new_xl = ((xl == 0 || get_sum(xl - 1, ptr, t) > 0) ? xl : query_U(xl - 1, ptr, t)); //to.push_back({cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr), new_xl, new_xr, ptr, t}); rec(new_xl, new_xr, ptr, t, cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr)); ptr = R[xr + 1][ptr] + 1; } } /* for (int i = 0; i < (int) to.size(); i++) { rec(to[i][1], to[i][2], to[i][3], to[i][4], to[i][0]); } */ } int biggest_stadium(int N, vector<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]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum[i][j] = a[i][j]; if (j > 0) { sum[i][j] += sum[i][j - 1]; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 1) { continue; } int p = j; while (p + 1 < n && a[i][p + 1] == 0) { p += 1; } for (int k = j; k <= p; k++) { L[i][k] = j; R[i][k] = p; } j = p; } } for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { if (a[i][j] == 1) { continue; } int p = i; while (p + 1 < n && a[p + 1][j] == 0) { p += 1; } for (int k = i; k <= p; k++) { U[k][j] = i; D[k][j] = p; } i = p; } } for (int i = 2; i <= n; i++) { logs[i] = logs[i >> 1] + 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { st_U[0][i][j] = U[i][j]; st_D[0][i][j] = D[i][j]; } } for (int k = 1; k < LOG; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j + (1 << k) <= n; j++) { st_U[k][i][j] = max(st_U[k - 1][i][j], st_U[k - 1][i][j + (1 << (k - 1))]); st_D[k][i][j] = min(st_D[k - 1][i][j], st_D[k - 1][i][j + (1 << (k - 1))]); } } } for (int i = 0; i < n; i++) { for (int j = n - 1; j >= 0; j--) { if (a[i][j] == 1) { go[i][j] = (j == n - 1 ? n : go[i][j + 1]); } else { go[i][j] = j; } } } res = 0; vector<array<int, 4>> s; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 1) { continue; } if (j == 0 || a[i][j - 1] == 1) { if (i > 0 && get_sum(i - 1, j, R[i][j]) == 0) { continue; } if (i + 1 < n && get_sum(i + 1, j, R[i][j]) == 0 && ((j > 0 && a[i + 1][j - 1] == 0) || (R[i][j] + 1 < n && a[i + 1][R[i][j] + 1] == 0))) { continue; } s.push_back({(R[i][j] - j + 1), i, j, R[i][j]}); } } } sort(s.rbegin(), s.rend()); for (auto& p : s) { int i = p[1]; int l = p[2], r = p[3]; int from = query_U(i, l, r); int to = query_D(i, l, r); rec(from, to, l, r, (to - from + 1) * (r - l + 1)); } return res; }
#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...