제출 #1315449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315449		wangzhiyi33	구경하기 (JOI13_watching)	C++20	50 / 100	722 ms	31864 KiB

watching

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

int n,p,r;
vector<int>a;
int dp[2002][2002];

bool oke(int jrk){
    for(int q=1;q<=n;q++){
        int bsr=upper_bound(a.begin()+1,a.end(),a[q]-2*jrk)-a.begin()-1;
        int kcl=upper_bound(a.begin()+1,a.end(),a[q]-jrk)-a.begin()-1;

        for(int w=0;w<=r;w++){
            dp[q][w]=1e18;
            if(w>=1){
                dp[q][w]=min(dp[q][w-1],dp[bsr][w-1]);
            }

            dp[q][w]=min(dp[q][w],dp[kcl][w]+1);
        }
    }
    //if(jrk==3)cout<<dp[n][r]<<"K"<<endl;
    return dp[n][r]<=p;
}

signed main(){
    cin>>n>>p>>r;   
    for(int q=1;q<=n;q++){
        int x; cin>>x;
        a.push_back(x);
    } 
    a.push_back(0);
    sort(a.begin(),a.end());

    int l=1,r=1e9;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(oke(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

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