Submission #51438

#	Time	Username	Problem	Language	Result	Execution time	Memory
51438		IOrtroiii	Watching (JOI13_watching)	C++14	100 / 100	78 ms	8812 KiB

watching

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2005;
 
int n, p, q;
int a[N];
int rch1[N], rch2[N];
int f[N][N];
 
bool check(int w) {
	int pt = 1;
	for (int i = 1; i <= n; ++i) {
		while (pt <= n && a[i] + w > a[pt]) ++pt;
		rch1[i] = --pt;
	}
	pt = 1;
	for (int i = 1; i <= n; ++i) {
		while (pt <= n && a[i] + 2 * w > a[pt]) ++pt;
		rch2[i] = --pt;
	}
 
	for (int i = 0; i <= p; ++i) {
		for (int j = 0; j <= q; ++j) {
			f[i][j] = 0;
			if (i > 0) f[i][j] = max(f[i][j], rch1[f[i - 1][j] + 1]);
			if (j > 0) f[i][j] = max(f[i][j], rch2[f[i][j - 1] + 1]);
 			if (f[i][j] >= n) return true;
		}
	}
 	return false;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> p >> q;
	if (p + q >= n) return cout << 1 << '\n',0;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1);
	
	int l = 1, r = 1e9;
	while(l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid; 
		else l = mid + 1;
	}
	cout << l << '\n';
}

Compilation message (stderr)

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

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