Submission #472440

#	Time	Username	Problem	Language	Result	Execution time	Memory
472440		Jomnoi	Watching (JOI13_watching)	C++17	100 / 100	216 ms	16044 KiB

watching

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

const int N = 2e3+10;
const int INF = 1e9+7;

int a[N];
int dp[N][N];

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0);
    int n, p, q;
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if(p+q >= n) {
        cout << "1";
        return 0;
    }
    sort(a+1, a+n+1);
    int l = 1, r = INF, w = INF;
    while(l <= r) {
        int mid = (l+r)/2;
        int point_p = 1, point_q = 1;
        for(int i = 1; i <= n; i++) {
            while(a[i]-a[point_p] >= mid) {
                point_p++;
            }
            while(a[i]-a[point_q] >= 2*mid) {
                point_q++;
            }
            for(int j = 0; j <= p; j++) {
                dp[i][j] = INF;
                if(j) {
                    dp[i][j] = min(dp[i][j], dp[point_p-1][j-1]);
                }
                dp[i][j] = min(dp[i][j], dp[point_q-1][j]+1);
            }
        }
        int res = INF;
        for(int i = 0; i <= p; i++) {
            res = min(res, dp[n][i]);
        }
        if(res > q) {
            l = mid+1;
        }
        else {
            r = mid-1;
            w = min(w, mid);
        }
    }
    cout << w;
    return 0;
}

/*
3 1 1
2
11
17

13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75
*/

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