oj.uz

Submission #1101646

# Submission time Handle Problem Language Result Execution time Memory
1101646 2024-10-16T13:40:55 Z Kirill22 Watching (JOI13_watching) C++17
50 / 100
 1000 ms 16268 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());
    auto upd = [&] (int pos, int w) {
        if (pos == n) {
            return n;
        }
//        debug(a, pos, w);
        return int(std::lower_bound(a.begin(), a.end(), a[pos] + w) - a.begin());
    };
    auto check = [&] (int w) -> bool {
        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], w));
                }
                if (j + 1 <= q) {
                    mx[i][j + 1] = max(mx[i][j + 1], upd(mx[i][j], 2 * w));
                }
            }
        }
//        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 460 KB Output is correct
6 Correct 3 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 336 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
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 937 ms 9388 KB Output is correct
4 Correct 64 ms 1220 KB Output is correct
5 Correct 137 ms 1148 KB Output is correct
6 Execution timed out 1070 ms 16268 KB Time limit exceeded
7 Halted 0 ms 0 KB -