Submission #51545

#	Time	Username	Problem	Language	Result	Execution time	Memory
51545		tranxuanbach	Watching (JOI13_watching)	C++17	100 / 100	337 ms	32252 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2005;
int n, p, q, ans;
int a[N], cnt[N], max2w[N], maxw[N];
int f[N][N];
 
bool check(int mid){
	int cur1 = 1, cur2 = 1;
	for (int i = 1; i <= n; i++){
		for (; cur1 <= n && a[cur1] - a[i] + 1 <= mid; cur1++);
		maxw[i] = cur1 - 1;
		for (; cur2 <= n && a[cur2] - a[i] + 1 <= 2 * mid; cur2++);
		max2w[i] = cur2 - 1;
	}
	memset(f, -1, sizeof(f));
	f[1][0] = maxw[1];
	f[0][1] = max2w[1];
	if (maxw[1] == n || max2w[1] == n){
	    return true;
	}
	for (int i = 0; i <= p; i++){
		for (int j = 0; j <= q; j++){
			if (f[i][j] != -1){
				if (f[i][j] == n){
				    return true;
				}
				f[i][j + 1] = max(f[i][j + 1], max2w[f[i][j] + 1]);
				f[i + 1][j] = max(f[i + 1][j], maxw[f[i][j] + 1]);
			}
		}
	}
	return false;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	a[n + 1] = 1e9;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);	
	if (p + q >= n){
		cout << 1;
		return 0;
	}	
	int l = 1, r = a[n] - a[1] + 1;
	while (l <= r){
		int mid = (l + r) / 2;
		bool kt = check(mid);
		if (kt){
			ans = mid;
			r = mid - 1;
		}
		else{
		    l = mid + 1;
		}
	}
	cout << ans;
}

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