Submission #1251861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251861		elotelo966	Watching (JOI13_watching)	C++20	50 / 100	66 ms	1352 KiB

watching

#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;

map<pair<int,pair<int,int>>,int> dp;

inline int f(int sira,int cur_p,int cur_q){
	if(sira>n){
		return 1;
	}
	if(dp.find({sira,{cur_p,cur_q}})!=dp.end())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=max(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=max(cev,f(ol+1,cur_p,cur_q+1));
	}
	return dp[{sira,{cur_p,cur_q}}]=cev;
}

inline int check(int x){
	dp.clear();
	w=x;
	int tut=f(1,0,0);
	return tut;
}

int 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;
}

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