Submission #822613

#	Time	Username	Problem	Language	Result	Execution time	Memory
822613		vjudge1	Watching (JOI13_watching)	C++17	100 / 100	346 ms	31828 KiB

watching

#include <bits/stdc++.h>
#define ll long long
#define sp << " "
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
ll n, p, q, a[2005], dp[2005][2005], k, l;

bool check(ll mid){
	memset(dp,63,sizeof(dp));
	dp[0][0]=0;
	k=1,l=1;
	for(ll i = 1; i <= n; i++){
		while(a[i]-a[k]+1>mid) k++;
		while(a[i]-a[l]+1>2*mid) l++;
		for(ll j = 0; j <= q; j++){
			dp[i][j]=dp[k-1][j]+1;
			if(j>0) dp[i][j]=min(dp[i][j],dp[l-1][j-1]);
		}
	}
	for(ll i = 0; i <= q; i++) if(dp[n][i]<=p) return true;
	return false; 
}
int main(){
    faster;
    cin >> n >> p >> q;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    if(p>=n||q>=n){
    	cout << 1;
    	return 0;
    }
    ll l = 1, r = 1e15, mid;
    while(l<=r){
    	mid=(l+r)/2;
    	if(!check(mid)) l=mid+1;
    	else r=mid-1;
    }
    cout << l;
    return 0;
}

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