oj.uz

Submission #571953

# Submission time Handle Problem Language Result Execution time Memory
571953 2022-06-03T08:04:39 Z 1ne Watching (JOI13_watching) C++14
0 / 100
 8 ms 684 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 = 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));
		dp[0][0] = 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.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 8 ms 684 KB Output isn't correct
8 Halted 0 ms 0 KB -