Submission #1071095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071095		thinknoexit	Cultivation (JOI17_cultivation)	C++17	30 / 100	1947 ms	596 KiB

cultivation

#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++) {
        int all = s[i] - 1;
        up.insert(all);
        up.insert(all / 2);
        up.insert((all + 1) / 2);
        all = r - s[i];
        down.insert(all);
        down.insert(all / 2);
        down.insert((all + 1) / 2);
    }
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            int all = abs(s[i] - s[j]) - 1;
            up.insert(all + 1);
            down.insert(all + 1);
            if (all <= 0) continue;
            up.insert((all + 1) / 2);
            down.insert((all + 1) / 2);
            if (all > 1) {
                up.insert(all / 2);
                down.insert(all / 2);
            }
        }
    }
    // 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();
            if (event[0].first != 1) continue;
            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;
                }
                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;
}

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