Submission #1197840

#TimeUsernameProblemLanguageResultExecution timeMemory
1197840og_matveychick1Cultivation (JOI17_cultivation)C++20
0 / 100
3 ms784 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, _x[N], _y[N], ps[N], pL[N][N], pR[N][N], pmx[N][N]; void prec() { for (ll gl = 0; gl < n; gl++) { for (ll gr = gl; gr < n; gr++) { vector<ll> a; for (ll i = gl; i <= gr; i++) a.push_back(y[i]); sort(a.begin(), a.end()); pL[gl][gr] = a[0]; pR[gl][gr] = r - 1 - a[gr - gl]; for (ll i = 1; i < a.size(); i++) pmx[gl][gr] = max(pmx[gl][gr], a[i] - a[i - 1] - 1); } } } 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]--; iota(ps, ps + n, 0); sort(ps, ps + n, [&](ll a, ll b) { return x[a] < x[b]; }); for (ll i = 0; i < n; i++) _x[i] = x[ps[i]], _y[i] = y[ps[i]]; for (ll i = 0; i < n; i++) swap(x[i], _x[i]), swap(y[i], _y[i]); prec(); for (ll up = 0; up < n; up++) { // n vll cup; for (ll i = 0; i < n; i++) { cup.push_back(r - 1 - x[i]); for (ll j = i; j < n; j++) { cup.push_back(max(0ll, abs(x[i] - x[j]) - 1 - x[up])); } } sort(cup.begin(), cup.end()); cup.resize(unique(cup.begin(), cup.end()) - cup.begin()); for (ll dn = 0; dn < cup.size(); dn++) { // n^3 long long mx = 0, L = 0, R = 0; vector<ll> cp{0, r - 1}; for (ll i = 0; i < n; i++) { // n^4 cp.push_back(min(r - 1, max(0ll, x[i] - x[up] + 0))); cp.push_back(max(0ll, min(r - 1, x[i] + cup[dn] + 1))); } sort(cp.begin(), cp.end()); cp.resize(unique(cp.begin(), cp.end()) - cp.begin()); ll itl = 0, itr = -1; for (auto p: cp) { // n^4 while (itl < n && x[itl] + cup[dn] < p) itl++; while (itr + 1 < n && x[itr + 1] - x[up] <= p) itr++; if (itl > itr) { mx = 1e18; break; } mx = max(mx, pmx[itl][itr]); L = max(L, pL[itl][itr]); R = max(R, pR[itl][itr]); } ans = min(ans, max(mx, L + R) + cup[dn] + x[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...