oj.uz

Submission #399860

# Submission time Handle Problem Language Result Execution time Memory
399860 2021-05-06T18:27:41 Z nikatamliani Watching (JOI13_watching) C++14
100 / 100
 245 ms 16068 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 15948 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 90 ms 15992 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 90 ms 15984 KB Output is correct
8 Correct 86 ms 15948 KB Output is correct
9 Correct 87 ms 16068 KB Output is correct
10 Correct 94 ms 15984 KB Output is correct
11 Correct 88 ms 15920 KB Output is correct
12 Correct 88 ms 15948 KB Output is correct
13 Correct 89 ms 15948 KB Output is correct
14 Correct 87 ms 15992 KB Output is correct
15 Correct 88 ms 16068 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16000 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 115 ms 15948 KB Output is correct
8 Correct 119 ms 15908 KB Output is correct
9 Correct 161 ms 15948 KB Output is correct
10 Correct 245 ms 16000 KB Output is correct
11 Correct 105 ms 15948 KB Output is correct
12 Correct 186 ms 15948 KB Output is correct
13 Correct 120 ms 15948 KB Output is correct
14 Correct 112 ms 16004 KB Output is correct
15 Correct 109 ms 15948 KB Output is correct