oj.uz

Submission #1101648

# Submission time Handle Problem Language Result Execution time Memory
1101648 2024-10-16T13:43:25 Z Kirill22 Watching (JOI13_watching) C++17
100 / 100
 376 ms 16272 KB 
#include "bits/stdc++.h"

using namespace std;

//#include "debug.h"

void solve() {
    int n, p, q;
    cin >> n >> p >> q;
    p = min(p, n);
    q = min(q, n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    vector<int> go(n), go2(n);
    auto upd = [&] (int pos, int w) {
        if (pos == n) {
            return n;
        }
//        debug(a, pos, w);
        return w == 1 ? go[pos] : go2[pos];
    };
    auto check = [&] (int w) -> bool {
        if (w * 1ll * p + 2ll * w * q >= (long long) 1e9) {
            return true;
        }
        for (int pos = 0; pos < n; pos++) {
            go[pos] = int(std::lower_bound(a.begin(), a.end(), a[pos] + w) - a.begin());
            go2[pos] = int(std::lower_bound(a.begin(), a.end(), a[pos] + 2 * w) - a.begin());
        }
        vector<vector<int>> mx(p + 1, vector<int> (q + 1));
        for (int i = 0; i <= p; i++) {
            for (int j = 0; j <= q; j++) {
                if (i + 1 <= p) {
                    mx[i + 1][j] = max(mx[i + 1][j], upd(mx[i][j], 1));
                }
                if (j + 1 <= q) {
                    mx[i][j + 1] = max(mx[i][j + 1], upd(mx[i][j], 2));
                }
            }
        }
//        debug(w, mx);
        return mx[p][q] == n;
    };
    int l = 0, r = (int) 1e9;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << r << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 508 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 209 ms 9372 KB Output is correct
4 Correct 19 ms 1152 KB Output is correct
5 Correct 19 ms 1104 KB Output is correct
6 Correct 376 ms 16272 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 13 ms 856 KB Output is correct
9 Correct 13 ms 872 KB Output is correct
10 Correct 22 ms 1440 KB Output is correct
11 Correct 22 ms 1308 KB Output is correct
12 Correct 106 ms 4352 KB Output is correct
13 Correct 5 ms 336 KB Output is correct
14 Correct 7 ms 480 KB Output is correct
15 Correct 5 ms 336 KB Output is correct