제출 #840704

#제출 시각아이디문제언어결과실행 시간메모리
840704PurpleCrayon축구 경기장 (IOI23_soccer)C++17
70 / 100
4582 ms1027788 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; #define ar array #define sz(v) int(v.size()) typedef long long ll; const int INF = 1e9+10; const int M = 2e3+10; struct Sparse { vector<vector<int>> sparse; Sparse() {} Sparse(vector<int>& v) { int n = v.size(); sparse.push_back(v); for (int i = 1; (1 << i) <= n; i++) { sparse.push_back(vector<int>(n - (1 << i) + 1)); for (int j = 0; j + (1 << i) <= n; j++) { sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]); } } } int qry(int l, int r) { assert(l <= r); int b = 31 - __builtin_clz(r - l + 1); // cerr << "> " << l << ' ' << r << '' return min(sparse[b][l], sparse[b][r - (1 << b) + 1]); } } ones[M], twos[M]; int check_full(int N, std::vector<std::vector<int>> F) { vector<int> one, two; vector<pair<int, int>> ranges; int ans = 0; for (int i = 0; i < N; i++) { int mn = N, mx = -1, cnt = 0; for (int j = 0; j < N; j++) { if (!F[i][j]) { mn = min(mn, j); mx = max(mx, j); cnt++; ans++; } } if (cnt && cnt != mx - mn + 1) return 0; one.push_back(mn); two.push_back(mx); if (cnt) ranges.push_back({mn, mx}); } auto contains = [&](pair<int, int> p1, pair<int, int> p2) { return p1.first <= p2.first && p2.second <= p1.second; }; for (auto p1 : ranges) { for (auto p2 : ranges) { if (!contains(p1, p2) && !contains(p2, p1)) return 0; } } int m1 = min_element(one.begin(), one.end()) - one.begin(); for (int i = m1; i > 0; i--) if (one[i] > one[i-1]) return 0; for (int i = m1; i < N-1; i++) if (one[i] > one[i+1]) return 0; int m2 = max_element(two.begin(), two.end()) - two.begin(); for (int i = m2; i > 0; i--) if (two[i] < two[i-1]) return 0; for (int i = m2; i < N-1; i++) if (two[i] < two[i+1]) return 0; return ans; } int run_subtask(int N, std::vector<std::vector<int>> F) { 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); } } } assert(false); } int get_cost(int i, int l, int r) { // int one = i + 1, two = N - i; // for (int i = l; i <= r; i++) one = min(one, up[i]); // for (int i = l; i <= r; i++) two = min(two, down[i]); // return max(0, one + two - 1); // cerr << l << ' ' << r << endl; return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1); } vector<int> impl[M][M]; vector<int> impr[M][M]; vector<int> has[M][M]; unordered_map<ll, int> dp; ll h(int a, int b, int c) { return (long long) a * M * M + b * M + c; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { int test = check_full(N, F); if (test) return test; int cnt_fill = 0; for (auto v : F) for (auto x : v) cnt_fill += x; if (cnt_fill == 1) { return run_subtask(N, F); } for (int i = 0; i < N; i++) { vector<int> up(N), down(N); for (int j = 0; j < N; j++) { while (i - up[j] >= 0 && !F[i - up[j]][j]) up[j]++; while (i + down[j] < N && !F[i + down[j]][j]) down[j]++; // if (i == 0) cerr << up[j] << ' ' << down[j] << endl; // if (i == 0) cerr << "> " << F[i][i + 1] } ones[i] = Sparse(up), twos[i] = Sparse(down); // vector<vector<int>> dp(N, vector<int>(N, -INF)); // for (int l = 0; l < N; l++) { // for (int r = N-1; r >= l; r--) { // dp[l][r] = get_cost(l, r) * (r - l + 1); // } // } // for (int l = 0; l < N; l++) { // for (int r = N-1; r > l; r--) if (dp[l][r] >= 0) { // // if (i == 2) cerr << l << ' ' << r << ' ' << dp[l][r] << endl; // // if (i == 2 && l == 0 && r == 4) cerr << ">> " << get_cost(l + 1, r) << ' ' << get_cost(l, r) << endl; // dp[l+1][r] = max(dp[l+1][r], (get_cost(l + 1, r) - get_cost(l, r)) * (r - l) + dp[l][r]); // dp[l][r-1] = max(dp[l][r-1], (get_cost(l, r - 1) - get_cost(l, r)) * (r - l) + dp[l][r]); // } // } // for (int i = 0; i < N; i++) // for (int j = 0; j < N; j++) { // ans = max(ans, dp[i][j]); // } } auto add_imp = [&](int i, int l, int r) { has[l][r].push_back(i); impl[i][l].push_back(r); impr[i][r].push_back(l); }; for (int i = 0; i < N; i++) { vector<int> blocks{-1}; for (int j = 0; j < N; j++) if (F[i][j]) blocks.push_back(j); blocks.push_back(N); for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) { int l = blocks[j-1]+1, r = blocks[j]-1; for (int k = l; k <= r; k++) { add_imp(i, k, r); if (k != r) add_imp(i, l, k); } } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { sort(impl[i][j].begin(), impl[i][j].end()); sort(impr[i][j].begin(), impr[i][j].end()); } } auto upd = [&](int ni, int l, int r, int x, int cur_cost) { if (ni < 0 || ni >= N) return; int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), l) - impr[ni][r].begin(); if (nl < sz(impr[ni][r])) { nl = impr[ni][r][nl]; dp[h(ni, nl, r)] = max(dp[h(ni, nl, r)], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1)); } int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), r) - impl[ni][l].begin() - 1; if (nr >= 0) { nr = impl[ni][l][nr]; dp[h(ni, l, nr)] = max(dp[h(ni, l, nr)], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1)); } }; // cerr << (double) clock() / CLOCKS_PER_SEC << endl; for (int l = 0; l < N; l++) { for (int r = N-1; r >= 0; r--) { for (int i : has[l][r]) { int cur_cost = get_cost(i, l, r); dp[h(i, l, r)] = max(dp[h(i, l, r)], cur_cost * (r - l + 1)); // cerr << l << ' ' << r << ' ' << i << ' ' << dp[{i, l, r}] << endl; int top = i - ones[i].qry(l, r); int bot = i + twos[i].qry(l, r); upd(i, l, r, dp[h(i, l, r)], cur_cost); upd(top, l, r, dp[h(i, l, r)], cur_cost); upd(bot, l, r, dp[h(i, l, r)], cur_cost); } } } int ans = 0; for (auto& [_, v] : dp) ans = max(ans, v); // cerr << (double) clock() / CLOCKS_PER_SEC << endl; 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...