Submission #1251752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251752		kerem	Watching (JOI13_watching)	C++17	0 / 100	7 ms	320 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
#define N 2000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int n,p,q,a[N+5];
bool f(int w){
	pii dp[n];
	dp[0]={0,0};
	for(int i=1;i<=n;i++){
		dp[i]={inf,inf};
		for(int j=0;j<i;j++){
			if(a[i]-a[j+1]+1<=w && dp[j].fr-dp[j].sc!=p)
				dp[i]=min(dp[i],make_pair(dp[j].fr+1,dp[j].sc));
			else if(a[i]-a[j+1]+1<=2*w && dp[j].sc!=q)
				dp[i]=min(dp[i],make_pair(dp[j].fr+1,dp[j].sc+1));
		}
	}
	//~ for(int i=0;i<=n;i++)
		//~ cout << dp[i].fr sp dp[i].sc << endl;
	return (dp[n].fr!=inf);
}
void solve(){
	cin >> n >> p >> q;
	for(int i=1;i<=n;i++) cin >> a[i];
	if(n<=p+q){
		cout << 1;
		return;
	}
	sort(a+1,a+n+1);
	int l=1,r=inf;
	while(l<r){
		int mid=(l+r)/2;
		if(f(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << endl;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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