Submission #1197515

#TimeUsernameProblemLanguageResultExecution timeMemory
1197515og_matveychick1Cultivation (JOI17_cultivation)C++20
0 / 100
378 ms452 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; const ll N = 305; ll n, r, c, x[N], y[N], ans = 1e18; vll cup; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> r >> c >> n; for (ll i = 0; i < n; i++) cin >> x[i] >> y[i], x[i]--, y[i]--; cup.push_back(0); for (ll i = 0; i < n; i++) { cup.push_back(x[i]); cup.push_back(r - x[i] - 1); for (ll j = i + 1; j < n; j++) { cup.push_back(abs(x[i] - x[j])); if (x[i] != x[j]) cup.push_back(abs(x[i] - x[j]) - 1); } } sort(cup.begin(), cup.end()); cup.resize(unique(cup.begin(), cup.end()) - cup.begin()); for (ll up = 0; up < cup.size(); up++) { for (ll dn = 0; dn < cup.size(); dn++) { ll mx = 0, L = 0, R = 0; vector<ll> cp{0, r - 1}; vector<array<ll, 3>> scan; for (ll i = 0; i < n; i++) { scan.push_back({max(0ll, x[i] - cup[up]), 1, y[i]}); scan.push_back({min(r, x[i] + cup[dn] + 1), -1, y[i]}); cp.push_back(min(r - 1, max(0ll, x[i] - cup[up] + 0))); cp.push_back(max(0ll, min(r - 1, x[i] + cup[dn] + 1))); } sort(scan.begin(), scan.end()); sort(cp.begin(), cp.end()); cp.resize(unique(cp.begin(), cp.end()) - cp.begin()); multiset<ll> s; s.insert(-1); s.insert(c); multiset<ll> q; q.insert(c); ll it = 0; for (auto p: cp) { while (it < scan.size() && scan[it][0] <= p) { ll f = scan[it][2]; if (scan[it][1] == 1) { s.insert(f); auto i = s.find(f), l = prev(i), r = next(i); q.erase(q.find(*r - *l - 1)); q.insert(*r - f - 1); q.insert(f - *l - 1); } else { auto i = s.find(f), l = prev(i), r = next(i); q.insert(*r - *l - 1); q.erase(q.find(*r - f - 1)); q.erase(q.find(f - *l - 1)); s.erase(s.find(f)); } it++; } if (s.size() == 2) mx = 1e18; else mx = max(mx, *--q.end()); L = max(L, *next(q.begin())); R = max(R, c - 1 - *prev(--q.end())); } ans = min(ans, max(mx, L + R) + cup[dn] + cup[up]); } } cout << 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...