Submission #1071034

#TimeUsernameProblemLanguageResultExecution timeMemory
1071034thinknoexitCultivation (JOI17_cultivation)C++17
0 / 100
1117 ms262144 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 303; int s[N], e[N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int r, c; cin >> r >> c; int n; cin >> n; for (int i = 1;i <= n;i++) cin >> s[i] >> e[i]; set<int> up, down; // for (int i = 1;i <= n;i++) { // up.insert(s[i] - 1); // down.insert(r - s[i]); // } for (int i = 0;i < r;i++) up.insert(i), down.insert(i); // iterate for all O(n ^ 2) ll mn = r + c; for (auto& u : up) { for (auto& d : down) { bool ch = 1; int mx = 0; int dl = 0, dr = 0; multiset<int> ms; vector<pair<int, int>> event; for (int i = 1;i <= n;i++) { event.push_back({ max(1, s[i] - u), e[i] }); event.push_back({ min(r + 1, s[i] + d + 1), -e[i] }); } ms.insert(0); ms.insert(c + 1); sort(event.begin(), event.end()); int sz = event.size(); for (int i = 0, j;i < sz;i = j) { if (event[i].first == r + 1) break; for (j = i;j < sz && event[i].first == event[j].first;j++) { int v = event[j].second; if (v < 0) ms.erase(ms.find(-v)); else ms.insert(v); } for (j = i;j < sz && event[i].first == event[j].first;j++) { int v = abs(event[j].second); int l = *(--ms.lower_bound(abs(v))); int r = *(ms.upper_bound(abs(v))); if (ms.find(v) == ms.end()) mx = max(mx, r - l - 1); else mx = max({ mx, v - l - 1, r - v - 1 }); } if ((int)ms.size() == 2) { ch = 0; break; } dl = max(dl, *(ms.upper_bound(0)) - 1); dr = max(dr, c - *(--ms.lower_bound(c + 1))); } if (ch) { mn = min(mn, 0ll + u + d + max(dl + dr, mx)); //cout << u << ' ' << d << ' ' << dl << ' ' << dr << ' ' << mx << '\n'; } } } cout << mn << '\n'; 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...