oj.uz

Submission #51438

# Submission time Handle Problem Language Result Execution time Memory
51438 2018-06-18T02:24:05 Z IOrtroiii Watching (JOI13_watching) C++14
100 / 100
 78 ms 8812 KB 
#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

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

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 808 KB Output is correct
12 Correct 2 ms 808 KB Output is correct
13 Correct 2 ms 808 KB Output is correct
14 Correct 3 ms 808 KB Output is correct
15 Correct 2 ms 808 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 808 KB Output is correct
2 Correct 2 ms 808 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 808 KB Output is correct
6 Correct 2 ms 808 KB Output is correct
7 Correct 3 ms 808 KB Output is correct
8 Correct 14 ms 1508 KB Output is correct
9 Correct 15 ms 3940 KB Output is correct
10 Correct 24 ms 8812 KB Output is correct
11 Correct 12 ms 8812 KB Output is correct
12 Correct 78 ms 8812 KB Output is correct
13 Correct 3 ms 8812 KB Output is correct
14 Correct 3 ms 8812 KB Output is correct
15 Correct 3 ms 8812 KB Output is correct