oj.uz

Submission #26824

# Submission time Handle Problem Language Result Execution time Memory
26824 2017-07-06T07:42:40 Z szawinis Watching (JOI13_watching) C++14
100 / 100
 276 ms 17828 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (2e3)+1, INF = 1e8;

int n, p, q, a[MAX], dp[MAX][MAX];
bool check(int len) {
	for(int i = 1, x = 1, y = 1; i <= n; i++) {
		while(a[i] - a[x] + 1 > len) x++;
		while(a[i] - a[y] + 1 > 2*len) y++;
		for(int j = 0; j <= min(p, n); j++) dp[i][j] = dp[y-1][j] + 1;
		for(int j = 1; j <= min(p, n); j++) dp[i][j] = min(dp[x-1][j-1], dp[i][j]);
	}
	bool ret = false;
	for(int j = 0; j <= min(p, n); j++) ret |= dp[n][j] <= q;
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	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;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:25:14: 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 0 ms 17828 KB Output is correct
2 Correct 0 ms 17828 KB Output is correct
3 Correct 0 ms 17828 KB Output is correct
4 Correct 0 ms 17828 KB Output is correct
5 Correct 0 ms 17828 KB Output is correct
6 Correct 0 ms 17828 KB Output is correct
7 Correct 0 ms 17828 KB Output is correct
8 Correct 0 ms 17828 KB Output is correct
9 Correct 0 ms 17828 KB Output is correct
10 Correct 0 ms 17828 KB Output is correct
11 Correct 0 ms 17828 KB Output is correct
12 Correct 0 ms 17828 KB Output is correct
13 Correct 0 ms 17828 KB Output is correct
14 Correct 0 ms 17828 KB Output is correct
15 Correct 0 ms 17828 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17828 KB Output is correct
2 Correct 0 ms 17828 KB Output is correct
3 Correct 199 ms 17828 KB Output is correct
4 Correct 263 ms 17828 KB Output is correct
5 Correct 13 ms 17828 KB Output is correct
6 Correct 276 ms 17828 KB Output is correct
7 Correct 6 ms 17828 KB Output is correct
8 Correct 16 ms 17828 KB Output is correct
9 Correct 96 ms 17828 KB Output is correct
10 Correct 246 ms 17828 KB Output is correct
11 Correct 16 ms 17828 KB Output is correct
12 Correct 123 ms 17828 KB Output is correct
13 Correct 0 ms 17828 KB Output is correct
14 Correct 3 ms 17828 KB Output is correct
15 Correct 6 ms 17828 KB Output is correct