Submission #840640

#TimeUsernameProblemLanguageResultExecution timeMemory
840640arbuzickSoccer Stadium (IOI23_soccer)C++17
6 / 100
263 ms47392 KiB
#include <bits/stdc++.h> using namespace std; int biggest_stadium(int n, vector<vector<int>> f) { vector<vector<int>> pr_sum(n + 1, vector<int>(n + 1)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { f[i][j] ^= 1; pr_sum[i + 1][j + 1] = pr_sum[i + 1][j] + pr_sum[i][j + 1] - pr_sum[i][j] + f[i][j]; } } if (pr_sum[n][n] == n * n - 1) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (!f[i][j]) { return n * n - min(i + 1, n - i) * min(j + 1, n - j); } } } } vector<vector<int>> ll(n, vector<int>(n, -1)), rr(n, vector<int>(n, n)), dd(n, vector<int>(n, n)); for (int i = n - 1; i >= 0; --i) { for (int j = 0; j < n; ++j) { if (!f[i][j]) { ll[i][j] = j; dd[i][j] = i; } else { if (j > 0) { ll[i][j] = ll[i][j - 1]; } if (i + 1 < n) { dd[i][j] = dd[i + 1][j]; } } } for (int j = n - 1; j >= 0; --j) { if (!f[i][j]) { rr[i][j] = j; } else if (j + 1 < n) { rr[i][j] = rr[i][j + 1]; } } } bool check = true; auto get = [&](int i1, int j1, int i2, int j2) { return pr_sum[i2][j2] - pr_sum[i1][j2] - pr_sum[i2][j1] + pr_sum[i1][j1]; }; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (!f[i][j]) { continue; } int l = ll[i][j], r = rr[i][j], d = dd[i][j]; if (get(i, 0, i + 1, l + 1) || get(i, d, i + 1, n) || get(i, r, i + 1, n)) { check = false; } if (l > -1 && d < n) { if (pr_sum[n][l] - pr_sum[d + 1][0]) { check = false; } } if (r < n && d < n) { if (pr_sum[n][n] - pr_sum[d + 1][n] - pr_sum[n][r + 1] + pr_sum[d + 1][r + 1]) { check = false; } } } } if (check) { return pr_sum[n][n]; } else { return pr_sum[n][n] - 1; } }
#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...