oj.uz

Submission #985910

# Submission time Handle Problem Language Result Execution time Memory
985910 2024-05-19T09:57:49 Z alextodoran Cultivation (JOI17_cultivation) C++17
5 / 100
 7 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 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 6 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 6 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 6 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -