Submission #950470

#TimeUsernameProblemLanguageResultExecution timeMemory
950470arbuzickGarden (JOI23_garden)C++17
29 / 100
3090 ms13744 KiB
#include <bits/stdc++.h> using namespace std; void solve() { int n, m, d; cin >> n >> m >> d; vector<int> p(n), q(n); for (int i = 0; i < n; ++i) { cin >> p[i] >> q[i]; } vector<int> r(m), s(m); for (int i = 0; i < m; ++i) { cin >> r[i] >> s[i]; } int ans = d * d; if (m <= 8) { vector<int> p_nw, q_nw; for (int i = 0; i < n; ++i) { p_nw.push_back(p[i]); p_nw.push_back(p[i] + d); q_nw.push_back(q[i]); q_nw.push_back(q[i] + d); } sort(p_nw.begin(), p_nw.end()); sort(q_nw.begin(), q_nw.end()); for (int mask = 0; mask < (1 << m); ++mask) { int mnx = d, mny = d; for (int i = 0; i < d; ++i) { int posx = lower_bound(p_nw.begin(), p_nw.end(), i) - p_nw.begin(); int rx = p_nw[posx + n - 1] + 1; for (int j = 0; j < m; ++j) { if (mask & (1 << j)) { if (i <= r[j]) { rx = max(rx, r[j] + 1); } else { rx = max(rx, r[j] + d + 1); } } } mnx = min(mnx, rx - i); int posy = lower_bound(q_nw.begin(), q_nw.end(), i) - q_nw.begin(); int ry = q_nw[posy + n - 1] + 1; for (int j = 0; j < m; ++j) { if (!(mask & (1 << j))) { if (i <= s[j]) { ry = max(ry, s[j] + 1); } else { ry = max(ry, s[j] + d + 1); } } } mny = min(mny, ry - i); } ans = min(ans, mnx * mny); } } else { for (int lx = 0; lx < d; ++lx) { for (int ly = 0; ly < d; ++ly) { for (int rx = lx + 1; rx <= lx + d; ++rx) { int ry = ly + 1; bool check = true; for (int i = 0; i < n; ++i) { if (!(lx <= p[i] && p[i] < rx) && !(lx <= p[i] + d && p[i] + d < rx)) { check = false; } if (ly <= q[i]) { ry = max(ry, q[i] + 1); } else { ry = max(ry, q[i] + d + 1); } } if (!check) { continue; } for (int i = 0; i < m; ++i) { if (!(lx <= r[i] && r[i] < rx) && !(lx <= r[i] + d && r[i] + d < rx)) { if (ly <= s[i]) { ry = max(ry, s[i] + 1); } else { ry = max(ry, s[i] + d + 1); } } } if (check) { ans = min(ans, (rx - lx) * (ry - ly)); } } } } } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } 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...