Submission #531773

#	Time	Username	Problem	Language	Result	Execution time	Memory
531773		pokmui9909	Watching (JOI13_watching)	C++17	100 / 100	237 ms	31820 KiB

watching

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

ll N, P, Q;
ll A[2005];
ll B[2005][2];
ll D[2005][2005];
ll f(ll W){
    for(int i = 1; i <= N; i++){
        B[i][0] = upper_bound(A, A + i, A[i] - W) - A - 1;
        B[i][1] = upper_bound(A, A + i, A[i] - 2 * W) - A - 1;
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= N; j++){
            D[i][j] = D[B[i][1]][j] + 1;
            if(j >= 1) D[i][j] = min(D[i][j], D[B[i][0]][j - 1]);
        }
    }
    return D[N][min(P, N)];
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> P >> Q;
    A[0] = -1e15;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
    }
    sort(A + 1, A + N + 1);
    ll L = 1, R = 1e9;
    while(L <= R){
        ll m = (L + R) / 2;
        if(f(m) <= Q) R = m - 1;
        else L = m + 1;
    }
    cout << L;
}

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