Submission #1071052

#TimeUsernameProblemLanguageResultExecution timeMemory
1071052thinknoexitCultivation (JOI17_cultivation)C++17
0 / 100
1038 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 = LLONG_MAX; 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 (auto& v : ms) { if (v == c + 1) continue; int r = *(ms.upper_bound(abs(v))); mx = max(mx, r - v - 1); } if ((int)ms.size() == 2) { ch = 0; break; } int fl = *(ms.upper_bound(0)); int fr = *(--ms.lower_bound(c + 1)); dl = max(dl, fl - 1); dr = max(dr, c - fr); } 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...