Submission #946589

#	Time	Username	Problem	Language	Result	Execution time	Memory
946589		VMaksimoski008	Watching (JOI13_watching)	C++14	100 / 100	196 ms	16500 KiB

watching

#include <bits/stdc++.h>
using namespace std;

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

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

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

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

    auto f = [&](int m) {
        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(i=1; i<=n; i++) {
            while(v[i] - v[k] >= m) k++;
            while(v[i] - v[l] >= 2 * m) l++;
            for(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(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 m = (l + r) / 2;
        if(f(m)) ans = m, r = m - 1;
        else l = m + 1;
    }

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

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