oj.uz

Submission #571965

# Submission time Handle Problem Language Result Execution time Memory
571965 2022-06-03T08:09:46 Z 1ne Watching (JOI13_watching) C++14
0 / 100
 7 ms 492 KB 
#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;
	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,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]==LLONG_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;
			ans = mid;
		}
		else{
			left = mid + 1;
		}
	}
	cout<<left<<'\n';
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:16:12: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   16 |  long long ans = right;
      |            ^~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -