Submission #399860

#	Time	Username	Problem	Language	Result	Execution time	Memory
399860		nikatamliani	Watching (JOI13_watching)	C++14	100 / 100	245 ms	16068 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N = 2003;
int a[N], dp[N][N], n, q, p;
void mini(int &x, int y) {
	if(x > y) x = y;
}
bool check(int x) {
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			dp[i][j] = 1e9;
		}
		dp[0][i] = 0;
	}
	for(int i = 1; i <= n; ++i) {
		int id0 = i-1, id1 = i-1;
		while(id0 > 0 && a[i] - a[id0] + 1 <= x) --id0;
		while(id1 > 0 && a[i] - a[id1] + 1 <= 2*x) --id1;
		for(int j = 0; j <= p; ++j) {
			dp[i][j] = dp[id1][j]+1;
			if(j > 0) {
				mini(dp[i][j], dp[id0][j-1]);
			}
		}
	}
	return dp[n][p] <= q;
}
int main() {
	cin >> n >> p >> q;
	if(p + q >= n) {
		cout << 1 << '\n';
		return 0;
	}
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	sort(a+1, a+n+1);
	int l = 1, r = 1e9, ans = -1;
	while(r >= l) {
		int m = l + r >> 1;
		if(check(m)) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int m = l + r >> 1;
      |           ~~^~~

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