Submission #1101648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101648		Kirill22	Watching (JOI13_watching)	C++17	100 / 100	376 ms	16272 KiB

watching

#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 / 50
• Subtask 2: 50 / 50