Submission #1286738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286738		Sofiatpc	구경하기 (JOI13_watching)	C++20	0 / 100	75 ms	16140 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2005;
int a[MAXN], dp[MAXN][MAXN], n, p, q;

bool test(int w){
    for(int i = n; i >= 1; i--){
        int nxtp = upper_bound(a+1,a+1+n, a[i]+w-1)-a;
        int nxtq = upper_bound(a+1,a+1+n, a[i]+2*w-1)-a;

        for(int qtdp = 0; qtdp <= p; qtdp++){
            dp[i][qtdp] = dp[nxtq][qtdp]+1;
            if(qtdp > 0)dp[i][qtdp] = min(dp[i][qtdp], dp[nxtp][qtdp-1]);
        }
    }
    return dp[1][p] <= q;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a+1,a+1+n);

    int l = 0, r = 1e9;
    while(l != r){
        int mid = (l+r)/2;
        if(test(mid))r = mid;
        else l = mid+1;
    }
    cout<<l<<"\n";

}

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