제출 #1197556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197556		og_matveychick1	Cultivation (JOI17_cultivation)	C++20	0 / 100	1893 ms	448 KiB

cultivation

#include "bits/stdc++.h"

using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;


const ll N = 305;

ll n, r, c, x[N], y[N];
long long 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());
    ll xl = 0, xr = 0, xmn = 0;
    vll X;
    for (ll i = 0; i < n; i++) X.push_back(x[i]);
    sort(X.begin(), X.end());
    xl = X[0], xr = c - 1 - X[n - 1];
    for (int i = 1; i < X.size(); i++) xmn = max(xmn, X[i] - X[i - 1] - 1);
    for (ll up = 0; up < cup.size(); up++) {
        if (cup[up] < xl) continue;
        for (ll dn = 0; dn < cup.size(); dn++) {
            if (cup[dn] < xr || cup[up] + cup[dn] < xmn) continue;
            long long 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(0, 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(0, x[i] - cup[up] + 0)));
                cp.push_back(max(0, 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, (long long) *--q.end());
                L = max(L, (long long) *next(s.begin()));
                R = max(R, (long long) c - 1 - *prev(--s.end()));
            }
            ans = min(ans, max(mx, L + R) + cup[dn] + cup[up]);
        }
    }
    cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20