Submission #985897

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

cultivation

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 300;
const int INF = INT_MAX;

int H, W;
int N;
int X[N_MAX + 2], Y[N_MAX + 2];

int xs[N_MAX + 2], ys[N_MAX + 2];
int cntx, cnty;

int order[N_MAX + 2];

multiset <int> S;
multiset <int> diffs;

void add_S (int y) {
    multiset <int> :: iterator it = S.insert(y);
    if (it != S.begin()) {
        diffs.erase(diffs.find(*next(it) - *prev(it)));
        diffs.insert(*it - *prev(it));
    }
    diffs.insert(*next(it) - *it);
}
void del_S (int y) {
    multiset <int> :: iterator it = S.find(y);
    if (it != S.begin()) {
        diffs.erase(diffs.find(*it - *prev(it)));
        diffs.insert(*next(it) - *prev(it));
    }
    diffs.erase(diffs.find(*next(it) - *it));
    S.erase(it);
}

int solve (int h) {
    if (h == 0) {
        return INF;
    }
    S.clear(); S.insert(W + 1);
    diffs.clear();
    int w = 0;
    for (int k = 2, i = 1, j = 1; k <= cntx + 1; k++) {
        while (i <= N && X[order[i]] <= xs[k] - 1) {
            add_S(Y[order[i++]]);
        }
        while (j <= i && X[order[j]] + h < xs[k] - 1) {
            del_S(Y[order[j++]]);
        }
        if (S.empty() == true || *S.begin() != 1) {
            return INF;
        }
        w = max(w, *diffs.rbegin() - 1);
    }
    return h + w;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> H >> W;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
        xs[i] = X[i]; ys[i] = Y[i];
    }
    sort(xs + 1, xs + N + 1);
    sort(ys + 1, ys + N + 1);
    for (int i = N; i >= 1; i--) {
        X[i] -= (xs[1] - 1); Y[i] -= (ys[1] - 1);
        xs[i] -= (xs[1] - 1); ys[i] -= (ys[1] - 1);
    }
    cntx = (unique(xs + 1, xs + N + 1) - (xs + 1));
    cnty = (unique(ys + 1, ys + N + 1) - (ys + 1));
    xs[cntx + 1] = H + 1; ys[cnty + 1] = W + 1;
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return X[i] < X[j];
    });
    int answer = INF;
    for (int i = 1; i <= cntx; i++) {
        for (int j = i + 1; j <= cntx; j++) {
            answer = min(answer, solve(xs[j] - xs[i] - 1));
        }
        answer = min(answer, solve(H - xs[i]));
    }
    cout << answer << "\n";

    return 0;
}

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