oj.uz

답안 #985948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985948 2024-05-19T11:48:21 Z alextodoran Cultivation (JOI17_cultivation) C++17
35 / 100
 2000 ms 600 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 300;
const ll INF = LLONG_MAX;

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

int xs[N_MAX + 2], cntx;
int ys[N_MAX + 2], 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()) {
        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);
}

ll 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 (ll) 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]; ys[i] = Y[i];
    }
    sort(xs + 1, xs + N + 1);
    sort(ys + 1, ys + N + 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];
    });
    ll answer = INF;
    for (int kx = 1; kx <= cntx; kx++) {
        for (int ky = 1; ky <= cnty; ky++) {
            int dx = xs[kx] - 1, dy = ys[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++) {
                    if ((ll) (xs[j] - xs[i] - 1) + dy <= answer) {
                        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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 17 ms 348 KB Output is correct
18 Correct 295 ms 448 KB Output is correct
19 Correct 91 ms 348 KB Output is correct
20 Correct 7 ms 344 KB Output is correct
21 Execution timed out 2099 ms 344 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 17 ms 348 KB Output is correct
18 Correct 295 ms 448 KB Output is correct
19 Correct 91 ms 348 KB Output is correct
20 Correct 7 ms 344 KB Output is correct
21 Execution timed out 2099 ms 344 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 348 KB Output is correct
2 Correct 217 ms 348 KB Output is correct
3 Correct 98 ms 344 KB Output is correct
4 Correct 513 ms 440 KB Output is correct
5 Correct 406 ms 344 KB Output is correct
6 Correct 157 ms 444 KB Output is correct
7 Correct 133 ms 596 KB Output is correct
8 Correct 402 ms 444 KB Output is correct
9 Correct 159 ms 440 KB Output is correct
10 Correct 404 ms 436 KB Output is correct
11 Correct 439 ms 440 KB Output is correct
12 Correct 161 ms 344 KB Output is correct
13 Correct 13 ms 348 KB Output is correct
14 Correct 89 ms 348 KB Output is correct
15 Correct 349 ms 440 KB Output is correct
16 Correct 420 ms 440 KB Output is correct
17 Correct 367 ms 596 KB Output is correct
18 Correct 589 ms 344 KB Output is correct
19 Correct 395 ms 436 KB Output is correct
20 Correct 483 ms 440 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 348 KB Output is correct
2 Correct 217 ms 348 KB Output is correct
3 Correct 98 ms 344 KB Output is correct
4 Correct 513 ms 440 KB Output is correct
5 Correct 406 ms 344 KB Output is correct
6 Correct 157 ms 444 KB Output is correct
7 Correct 133 ms 596 KB Output is correct
8 Correct 402 ms 444 KB Output is correct
9 Correct 159 ms 440 KB Output is correct
10 Correct 404 ms 436 KB Output is correct
11 Correct 439 ms 440 KB Output is correct
12 Correct 161 ms 344 KB Output is correct
13 Correct 13 ms 348 KB Output is correct
14 Correct 89 ms 348 KB Output is correct
15 Correct 349 ms 440 KB Output is correct
16 Correct 420 ms 440 KB Output is correct
17 Correct 367 ms 596 KB Output is correct
18 Correct 589 ms 344 KB Output is correct
19 Correct 395 ms 436 KB Output is correct
20 Correct 483 ms 440 KB Output is correct
21 Execution timed out 2003 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 17 ms 348 KB Output is correct
18 Correct 295 ms 448 KB Output is correct
19 Correct 91 ms 348 KB Output is correct
20 Correct 7 ms 344 KB Output is correct
21 Execution timed out 2099 ms 344 KB Time limit exceeded
22 Halted 0 ms 0 KB -