Submission #1130606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130606		heey	Watching (JOI13_watching)	C++20	100 / 100	988 ms	15944 KiB

watching

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

int n, p, q;
int a[2001];
vector<vector<int>> dp;
bool moze(int w){
	dp.assign(q+1, vector<int>(p+1));
	dp[0][0] = 0;

	for(int bg = 0; bg <= q; bg++){
		for(int sm = 0; sm <= p; sm++){
			
			if(sm != 0) {
				int sx = a[dp[bg][sm-1] + 1] + w;
				sx = lower_bound(a+1, a+1+n, sx) - a - 1;
				dp[bg][sm] = max(dp[bg][sm], sx);
			}

			if(bg != 0){
				int bx = a[dp[bg-1][sm] + 1] + 2*w;
				bx = lower_bound(a+1, a+1+n, bx) - a - 1;
				dp[bg][sm] = max(dp[bg][sm], bx);
			}

			if(dp[bg][sm] == n) return true;
		}
	}
	return false;
}

signed main(){
	//ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++) cin>>a[i];
	p = min(p, n);
	q = min(q, n);
	sort(a+1, a + n+1);
	int l = 1, r = 1e9;
	while(l < r){
		int m = (l+r)>>1;
		if(moze(m)){
			r = m;
		}
		else {
			l = m+1;
		}
	}
	cout << r << '\n';
	return 0;
}

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