Submission #1251831

#TimeUsernameProblemLanguageResultExecution timeMemory
1251831elotelo966Watching (JOI13_watching)C++20
0 / 100
202 ms67872 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 205

typedef long long lo;

int n,p,q;

int a[lim];

int w;

int dp[lim][lim][lim];

inline int f(int sira,int cur_p,int cur_q){
	if(sira>n){
		return 1;
	}
	if(~dp[sira][cur_p][cur_q])return dp[sira][cur_p][cur_q];
	int cev=0;
	if(cur_p+1<=p){
		int ol=sira;
		for(int i=sira;i<=n;i++){
			if(a[i]-a[sira]<w){
				ol=i;
			}
		}
		cev+=f(ol+1,cur_p+1,cur_q);
	}
	if(cur_q+1<=q){
		int ol=sira;
		for(int i=sira;i<=n;i++){
			if(a[i]-a[sira]<2*w){
				ol=i;
			}
		}
		cev+=f(ol+1,cur_p,cur_q+1);
	}
	return dp[sira][cur_p][cur_q]=cev;
}

inline int check(int x){
	memset(dp,-1,sizeof(dp));
	w=x;
	int tut=f(1,0,0);
	return tut;
}

int32_t main(){
	faster
	cin>>n>>p>>q;
	FOR{
		cin>>a[i];
	}
	
	sort(a+1,a+1+n);
		
	int l=1,r=1e9;
	while(l<=r){
		int mi=(l+r)/2;
		if(check(mi)){
			r=mi-1;
		}
		else l=mi+1;
	}
	
	cout<<l<<'\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...