Submission #947120

#	Time	Username	Problem	Language	Result	Execution time	Memory
947120		sandrofeiqrishvili	Watching (JOI13_watching)	C++14	100 / 100	171 ms	32212 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define int long long
const int N = 2005, inf=1e18;
int n, p, q, a[N], dp[N][N],l1,l2;
set <pair <int, int> > s;
int ans;
bool check(int mid){
	for(int i=1; i<=n; i++){
		set <pair <int, int> > :: iterator it = s.lower_bound({a[i]-mid+1, 0});
		l1 = (*it).ss-1;
		it = s.lower_bound({a[i]-2*mid+1, 0});
		l2 = (*it).ss-1;
		for (int x=0; x<=n; x++) { 
			dp[i][x]=1e9;
			

			if(x==0){
				dp[i][x]=dp[l2][x]+1;
			}
			else{
				dp[i][x]=min(dp[l1][x-1], dp[l2][x]+1);
			}		
			if (i==n && x<=p && dp[i][x]<=q) return 1;
		}
	}
	return 0;
}
signed main() {
	cin >> n >> p >> q;
	
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	for (int i=1; i<=n; i++) {
		s.insert({a[i], i});
	}
	int l=1, r=1e9;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		} else l=mid+1;
	}
	cout << ans;
}

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