제출 #1286737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286737		Sofiatpc	구경하기 (JOI13_watching)	C++20	0 / 100	74 ms	16208 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;

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

    int l = 0, r = 5*1e8;
    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