Submission #571950

#	Time	Username	Problem	Language	Result	Execution time	Memory
571950		1ne	Watching (JOI13_watching)	C++14	0 / 100	8 ms	596 KiB

watching

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,p,q;cin>>n>>p>>q;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i)cin>>arr[i];
	sort(arr.begin(),arr.end());
	long long left = 1,right = 1e10;
	if (p + q >=n){
		cout<<1<<'\n';
		return 0;
	}
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		vector<vector<pair<int,int>>>adj(n);
		p = min(p,n);
		vector<vector<long long>>dp(n + 1,vector<long long>(p + 1,LLONG_MAX));
		for (int i = 0;i<=p;++i){
			dp[0][i] = 0;
		}
		for (int i = 0;i<n;++i){
			long long nxt = lower_bound(arr.begin(),arr.end(),arr[i] + 2 * u - 1) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u - 1) - arr.begin();
			while((nxt==n) || (arr[nxt] - arr[i] > 2 * u - 1))--nxt;
			while((nxt2==n) || (arr[nxt2] - arr[i] > u - 1))--nxt2;
			while(nxt + 1<n && arr[nxt + 1] - arr[i] <=2 * u - 1)++nxt;
			while(nxt2 + 1<n && arr[nxt2 + 1] - arr[i] <=u - 1)++nxt2;
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==LLONG_MAX)continue;
				dp[min(n,nxt + 1)][j] = min(dp[i][j] + 1,dp[min(n,nxt + 1)][j]);
				if (j + 1<=p)
					dp[min(n,nxt2 + 1)][j + 1] = min(dp[i][j],dp[min(n,nxt2 + 1)][j]);
			}
		}
		for (int i = 0;i<=p;++i){
			if (dp[n][i]<=q)return true;
		}
		return false;
	};
	while(left<=right){
		long long mid = (left + right)>>1;
		if (check(mid)){
			right = mid - 1;
			ans = mid;
		}
		else{
			left = mid + 1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
	

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