oj.uz

Submission #750257

# Submission time Handle Problem Language Result Execution time Memory
750257 2023-05-29T08:41:29 Z jmyszka2007 Watching (JOI13_watching) C++17
100 / 100
 122 ms 16064 KB 
#include <bits/stdc++.h>
using namespace std;
int tab[2010];
int dp[2010][2010];
int n, p, q;
bool check(int x) {
	int pop1 = 1;
	int pop2 = 1;
	for(int i = 1; i <= n; i++) {
		while(tab[i] - tab[pop1] + 1 > x) {
			pop1++;
		}
		while(tab[i] - tab[pop2] + 1 > 2 * x) {
			pop2++;
		}
		dp[i][0] = dp[pop2 - 1][0] + 1;
		for(int j = 1; j <= p; j++) {
			dp[i][j] = min(dp[pop1 - 1][j - 1], dp[pop2 - 1][j] + 1);
		}
	}
	int ans = 1e9;
	for(int j = 0; j <= p; j++) {
		ans = min(ans, dp[n][j]);
	}
	return ans <= q;
}
int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
	}
	sort(tab + 1, tab + n + 1);
	if(p >= n || q >= n) {
		cout << 1 << '\n';
		return 0;
	}
	int l = 1;
	int r = 1e9;
	while(l < r) {
		int mid = (l + r) / 2;
		if(check(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	cout << l << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 696 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 692 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 696 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8256 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 103 ms 15948 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 13 ms 9328 KB Output is correct
9 Correct 56 ms 14164 KB Output is correct
10 Correct 122 ms 16064 KB Output is correct
11 Correct 10 ms 9044 KB Output is correct
12 Correct 72 ms 16004 KB Output is correct
13 Correct 6 ms 8344 KB Output is correct
14 Correct 7 ms 8392 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct