Submission #1191767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191767		nagorn_ph	Watching (JOI13_watching)	C++20	100 / 100	854 ms	32020 KiB

watching

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
#define emb emplace_back

using namespace std;

const int inf = 1e9;

int n, p, q, go[2005][2]; 
set <int> aa;
vector <int> a;

bool can(int mid){
    // cout << mid << ": \n";
    vector <vector <int>> dp(p + 1, vector <int> (q + 1));
    int mx = 0;
    for (int i = 0; i < a.size(); i++) {
        go[i][0] = upper_bound(all(a), a[i] + mid - 1) - a.begin();
        go[i][1] = upper_bound(all(a), a[i] + mid + mid - 1) - a.begin();
        // cout << i << ": " << go[i][0] << " " << go[i][1] << "\n";
    }
    for (int i = 0; i <= p; i++) {
        for (int j = 0; j <= q; j++) {
            if (i == 0 && j == 0) continue;
            int pp = 0, qq = 0;
            if (i > 0) pp = go[dp[i - 1][j]][0];
            if (j > 0) qq = go[dp[i][j - 1]][1];
            pp = min(pp, (int)a.size() - 1);
            qq = min(qq, (int)a.size() - 1);
            dp[i][j] = max(pp, qq);
            // mx = max(mx, dp[i][j]);
            // cout << i << ", " << j << ": " << dp[i][j] << "\n";
        }
    }
    // cout << "--------------\n";
    return dp[p][q] >= (a.size() - 1);
}

int32_t main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> p >> q;
    if (p > n) p = n;
    if (q > n) q = n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        aa.insert(x);
    }
    a = vector <int> (all(aa));
    a.emb(1e9);
    can(2);
    int l = 1, r = inf, ans = inf;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (can(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    cout << ans;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50