Submission #946587

#	Time	Username	Problem	Language	Result	Execution time	Memory
946587		VMaksimoski008	Watching (JOI13_watching)	C++14	100 / 100	176 ms	16336 KiB

watching

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

vector<vector<int> > dp(2005, vector<int>(2005, 1e9));

int main() {
    int n, p, q;
    cin >> n >> p >> q;

    p = min(n, p);
    q = min(n, q);

    vector<int> v(n+1, -1e9);
    for(int i=1; i<=n; i++) cin >> v[i];
    sort(1+all(v));

    auto f = [&](int mid) {
        for(int i=0; i<=n; i++)
            for(int j=0; j<=p; j++) dp[i][j] = 1e9;
        dp[0][0] = 0;

        int k=0, l=0;
        for(int i=1; i<=n; i++) {
            while(v[i] - v[k] >= mid) k++;
            while(v[i] - v[l] >= 2ll * mid) l++;
            for(int j=0; j<=p; j++) {
                if(j) dp[i][j] = dp[k-1][j-1];
                dp[i][j] = min(dp[i][j], dp[l-1][j] + 1);
            }
        }

        for(int i=0; i<=p; i++)
            if(dp[n][i] <= q) return 1;
        return 0;
    };

    int l=1, r=1e9, ans = 1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(f(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    return 0;
}

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