Submission #976056

#	Time	Username	Problem	Language	Result	Execution time	Memory
976056		vjudge1	Watching (JOI13_watching)	C++17	100 / 100	284 ms	31968 KiB

watching

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

int nextp[2005],nextq[2005];
int a[2000+4];
int memo[2005][2005];
int n,p,q;

int dp(int idx,int p){
    if(p<0)return 1e18;
    if(idx==n+1)return 0;
    if(memo[idx][p]!=-1)return memo[idx][p];
    return memo[idx][p]=min(dp(nextp[idx],p-1),dp(nextq[idx],p)+1);
}

bool ok(int w){
    for(int k=1;k<=n;k++){
        nextp[k]=nextq[k]=n+1;
        for (int j =k+1; j <=n; j++) {
            if (a[j] - a[k] + 1 > w) {
                nextp[k] = j;
                break;
            }
        }
        for (int j = k+1; j <=n; j++) {
            if (a[j] - a[k] + 1 > 2 * w) {
                nextq[k] = j;
                break;
            }
        }
    }
    memset(memo,-1,sizeof memo);
    return dp(1,p)<=q;
}

signed main(){
    cin>>n>>p>>q;
    for(int k=1;k<=n;k++){
        cin>>a[k];
    }
    if(p+q>=n){
        cout<<1<<endl;
        return 0;
    }
    sort(a+1,a+n+1);
    int l=1,r=1e9,ans=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

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