Submission #985910

#	Time	Username	Problem	Language	Result	Execution time	Memory
985910		alextodoran	Cultivation (JOI17_cultivation)	C++17	5 / 100	7 ms	600 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], cntx;

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

int solve (int h) {
    S.clear(); S.insert(W + 1);
    diffs.clear();
//    cout << "solve(h=" << h << "):\n";
    int w = 0;
    for (int k = 2, i = 1, j = 1; k <= cntx + 1; k++) {
        if (xs[k] - 1 <= 0) {
            continue;
        }
//        cout << xs[k] - 1 << ":\n";
        while (i <= N && X[order[i]] <= xs[k] - 1) {
//            cout << "insert " << Y[order[i]] << "\n";
            add_S(Y[order[i++]]);
        }
        while (j < i && X[order[j]] + h < xs[k] - 1) {
//            cout << "delete " << Y[order[j]] << "\n";
            del_S(Y[order[j++]]);
        }
//        for (int d : diffs) {
//            cout << d << " ";
//        }
//        cout << "\n";
        if (S.empty() == true || *S.begin() > 1) {
            return INF;
        }
        w = max(w, *diffs.rbegin() - 1);
    }
//    cout << " => " << h << " + " << w << "\n";
    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];
    }
    sort(xs + 1, xs + N + 1);
    cntx = (unique(xs + 1, xs + N + 1) - (xs + 1));
    xs[cntx + 1] = H + 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 k = 1; k <= N; k++) {
        int dx = X[k] - 1, dy = Y[k] - 1;
        for (int i = 1; i <= N; i++) {
            X[i] -= dx; Y[i] -= dy;
        }
        for (int i = 1; i <= cntx; i++) {
            xs[i] -= dx;
        }
//        cout << "delta=(" << dx << "," << dy << ")\n";
        for (int i = 1; i <= cntx; i++) {
            for (int j = i + 1; j <= cntx + 1; j++) {
                answer = min(answer, solve(xs[j] - xs[i] - 1));
            }
        }
//        cout << "\n\n\n";
        for (int i = 1; i <= N; i++) {
            X[i] += dx; Y[i] += dy;
        }
        for (int i = 1; i <= cntx; i++) {
            xs[i] += dx;
        }
    }
    cout << answer << "\n";

    return 0;
}

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