Submission #571970

#	Time	Username	Problem	Language	Result	Execution time	Memory
571970		1ne	Watching (JOI13_watching)	C++14	0 / 100	764 ms	31968 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 = 0,right = 1e10;
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		vector<vector<pair<int,int>>>adj(n);
		p = min(p,n);
		q = min(q,n);
		vector<vector<long long>>dp(n + 1,vector<long long>(p + 1,INT_MAX));
		dp[0][0] = 0;
		for (int i = 0;i<n;++i){
			long long nxt = lower_bound(arr.begin(),arr.end(),arr[i] + 2 * u) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u) - arr.begin();
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==INT_MAX)continue;
				dp[nxt][j] = min(dp[i][j] + 1,dp[nxt][j]);
				if (j + 1<=p)
					dp[nxt2][j + 1] = min(dp[i][j],dp[nxt2][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