Submission #897495

#	Time	Username	Problem	Language	Result	Execution time	Memory
897495		yellowtoad	Watching (JOI13_watching)	C++17	100 / 100	235 ms	16188 KiB

watching

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, p, q, a[2010], l, r, w, ll, rr, mid, dp[2010][2010];

int main() {
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	l = 1; r = 1e9;
	while (l <= r) {
		w = (l+r)/2;
		for (int i = 0; i <= n; i++) for (int j = 0; j <= min(n,q); j++) dp[i][j] = 1e9;
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			ll = 1; rr = i-1;
			while (ll <= rr) {
				mid = (ll+rr)/2;
				if (a[mid] > a[i]-w) rr = mid-1;
				else ll = mid+1;
			}
			for (int j = 0; j <= min(n,q); j++) if (dp[rr][j] < p) dp[i][j] = dp[rr][j]+1;
			ll = 1; rr = i-1;
			while (ll <= rr) {
				mid = (ll+rr)/2;
				if (a[mid] > a[i]-2*w) rr = mid-1;
				else ll = mid+1;
			}
			for (int j = 1; j <= min(n,q); j++) dp[i][j] = min(dp[i][j],dp[rr][j-1]);
		}
		for (int j = 0; j <= min(n,q); j++) {
			if (dp[n][j] != 1e9) {
				r = w-1;
				goto skip;
			} 
		}
		l = w+1;
		skip:;
	}
	cout << l << endl;
}

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