Submission #985943

#	Time	Username	Problem	Language	Result	Execution time	Memory
985943		alextodoran	Cultivation (JOI17_cultivation)	C++17	35 / 100	2063 ms	604 KiB

cultivation

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

**/

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

const int N_MAX = 300;
const int INF = LLONG_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;
}

//bool brute (int U, int D, int L, int R) {
//    for (int x = 1; x <= H; x++) {
//        for (int y = 1; y <= W; y++) {
//            bool ok = false;
//            for (int i = 1; i <= N; i++) {
//                if (X[i] - U <= x && x <= X[i] + D && Y[i] - L <= y && y <= Y[i] + R) {
//                    ok = true;
//                    break;
//                }
//            }
//            if (ok == false) {
//                return false;
//            }
//        }
//    }
//    return true;
//}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    mt19937 rnd(time(0));

    cin >> H >> W;
    cin >> N;
//    H = W = 40; N = 10;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
//        X[i] = rnd() % H + 1;
//        Y[i] = rnd() % W + 1;
//        cout << X[i] << " " << Y[i] << "\n";
        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 kx = 1; kx <= N; kx++) {
        for (int ky = 1; ky <= N; ky++) {
            int dx = X[kx] - 1, dy = Y[ky] - 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";
//    for (int U = 0; U < H; U++) {
//        for (int D = 0; D < H; D++) {
//            for (int L = 0; L < W; L++) {
//                for (int R = 0; R < W; R++) {
//                    if (U + D + L + R < answer && brute(U, D, L, R) == true) {
//                        cout << U << " " << D << " " << L << " " << R << "\n";
//                        for (int i = 1; i <= N; i++) {
//                            cout << X[i] - U << " " << Y[i] - L << " ";
//                            cout << X[i] - U << " " << Y[i] + R << "\n";
//                            cout << X[i] - U << " " << Y[i] - L << " ";
//                            cout << X[i] + D << " " << Y[i] - L << "\n";
//                            cout << X[i] + D << " " << Y[i] + R << " ";
//                            cout << X[i] + D << " " << Y[i] - L << "\n";
//                            cout << X[i] + D << " " << Y[i] + R << " ";
//                            cout << X[i] - U << " " << Y[i] + R << "\n";
//                        }
//                        return 0;
//                    }
//                }
//            }
//        }
//    }

    return 0;
}

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