Submission #1071375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071375		thinknoexit	Cultivation (JOI17_cultivation)	C++17	0 / 100	1 ms	348 KiB

cultivation

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 303;
struct A {
    int gap, cost;
    bool operator < (const A& o) const {
        return gap > o.gap;
    }
};
pair<int, int> a[N];
int s[N], e[N], s2[N], e2[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];
        s2[i] = s[i];
        e2[i] = e[i];
        a[i].first = s[i];
        a[i].second = e[i];
    }
    sort(s2 + 1, s2 + 1 + n);
    sort(e2 + 1, e2 + 1 + n);
    int mnu = s2[1] - 1;
    int mnd = r - s2[n];
    int mnv = mnu + mnd;
    for (int i = 1;i < n;i++) {
        mnv = max(mnv, s2[i + 1] - s2[i] - 1);
    }
    int mnl = e2[1] - 1;
    int mnr = c - e2[n];
    int mnh = mnr + mnl;
    for (int i = 1;i < n;i++) {
        mnh = max(mnh, e2[i + 1] - e2[i] - 1);
    }
    sort(a + 1, a + 1 + n);
    vector<A> e;
    // minimum sum need
    // cost = max(remaining, mnh)
    for (int i = 1;i <= n;i++) {
        int mn = c + 1, mx = 0;
        int j = i + 1;
        for (int j = 1;j < i;j++) {
            if (a[i].first == a[j].first) continue;
            if (a[j].second <= a[i].second) mx = max(mx, a[j].second);
            else mn = min(mn, a[j].second);
        }
        if (mn != mx && a[i].first != 1)
            e.push_back({ a[i].first - 1, mn - mx - 1 }); // to corner
        mn = c + 1, mx = 0;
        while (a[i].first == a[j].first) j++;
        for (int k;j <= n;j = k) {
            for (k = j;k <= n && a[j].first == a[k].first;k++) {
                if (a[j].first - a[i].first - 1 > 0)
                    e.push_back({ a[j].first - a[i].first - 1,
                mn - mx - 1 });
            }
            for (k = j;k <= n && a[j].first == a[k].first;k++) {
                if (a[k].second <= a[i].second) mx = max(mx, a[k].second);
                else mn = min(mn, a[k].second);
            }
            if (mn == mx) break;
        }
        if (mn != mx && a[i].first != r)
            e.push_back({ r - a[i].first, mn - mx - 1 });
    }
    ll ans = LLONG_MAX;
    sort(e.begin(), e.end());
    int cost = 0; // column
    int sz = e.size();
    for (int i = 0;i < sz;i++) {
        //cout << e[i].gap << ' ' << e[i].cost << '\n';
        cost = max(cost, e[i].cost);
        if (i == sz) {
            ans = min(ans, 0ll + max(cost, mnh) + mnv);
        }
        else {
            ans = min(ans, 0ll + max(cost, mnh) + max(e[i + 1].gap, mnv));
        }
    }
    cout << ans << '\n';
    return 0;
}
/*
3 2
3 1
2 4
1 1
*/

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