Submission #1253028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253028		elotelo966	Watching (JOI13_watching)	C++20	50 / 100	114 ms	31972 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 2005

const int mod=998244353;

int n,p,q;

int a[lim];

int w;

int git[lim][2];

int dp[lim][lim];

inline int f(int sira,int cur_p){
	if(sira>n){
		return 0ll;
	}
	if(~dp[sira][cur_p])return dp[sira][cur_p];
	int cev=LLONG_MAX;
	if(cur_p+1<=p){
		cev=min(cev,f(git[sira][0],cur_p+1));
	}
	cev=min(cev,f(git[sira][1],cur_p)+((f(git[sira][1],cur_p)==LLONG_MAX?0ll:1ll)));
	return dp[sira][cur_p]=cev;
}

inline bool check(int ger){
	w=ger;
	FOR{
		int ol=i;
		for(int j=i;j<=n;j++){
			if(a[j]-a[i]<w){
				ol=j;
			}
			else break;
		}
		git[i][0]=ol+1;
	}
	FOR{
		int ol=i;
		for(int j=i;j<=n;j++){
			if(a[j]-a[i]<2*w){
				ol=j;
			}
			else break;
		}
		git[i][1]=ol+1;
	}
	
	memset(dp,-1,sizeof(dp));
	
	int tut=f(1,0);
	//cout<<w<<" "<<tut<<endl;
	return tut<=q;
}

int32_t main(){
	faster
	cin>>n>>p>>q;
	
	FOR{
		cin>>a[i];
	}
	
	sort(a+1,a+1+n);
		
	p=min(p,200ll);
	q=min(q,200ll);
	
	int l=1,r=1e10;
	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