제출 #950460

#제출 시각아이디문제언어결과실행 시간메모리
950460arbuzickGarden (JOI23_garden)C++17
6 / 100
3046 ms17888 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) { for (int mask = 0; mask < (1 << 8); ++mask) { 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); } for (int i = 0; i < m; ++i) { if (mask & (1 << i)) { p_nw.push_back(r[i]); p_nw.push_back(r[i] + d); } else { q_nw.push_back(s[i]); q_nw.push_back(s[i] + d); } } sort(p_nw.begin(), p_nw.end()); sort(q_nw.begin(), q_nw.end()); 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(); mnx = min(mnx, p_nw[posx + (int)p_nw.size() / 2 - 1] + 1 - i); int posy = lower_bound(q_nw.begin(), q_nw.end(), i) - q_nw.begin(); mny = min(mny, q_nw[posy + (int)q_nw.size() / 2 - 1] + 1 - 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) { for (int ry = ly + 1; ry <= ly + d; ++ry) { 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] && q[i] < ry) && !(ly <= q[i] + d && q[i] + d < ry)) { check = false; } } for (int i = 0; i < m; ++i) { if (!(lx <= r[i] && r[i] < rx) && !(lx <= r[i] + d && r[i] + d < rx) && !(ly <= s[i] && s[i] < ry) && !(ly <= s[i] + d && s[i] + d < ry)) { check = false; } } 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...