oj.uz

Submission #897495

# Submission time Handle Problem Language Result Execution time Memory
897495 2024-01-03T09:10:35 Z yellowtoad Watching (JOI13_watching) C++17
100 / 100
 235 ms 16188 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, p, q, a[2010], l, r, w, ll, rr, mid, dp[2010][2010];

int main() {
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	l = 1; r = 1e9;
	while (l <= r) {
		w = (l+r)/2;
		for (int i = 0; i <= n; i++) for (int j = 0; j <= min(n,q); j++) dp[i][j] = 1e9;
		dp[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			ll = 1; rr = i-1;
			while (ll <= rr) {
				mid = (ll+rr)/2;
				if (a[mid] > a[i]-w) rr = mid-1;
				else ll = mid+1;
			}
			for (int j = 0; j <= min(n,q); j++) if (dp[rr][j] < p) dp[i][j] = dp[rr][j]+1;
			ll = 1; rr = i-1;
			while (ll <= rr) {
				mid = (ll+rr)/2;
				if (a[mid] > a[i]-2*w) rr = mid-1;
				else ll = mid+1;
			}
			for (int j = 1; j <= min(n,q); j++) dp[i][j] = min(dp[i][j],dp[rr][j-1]);
		}
		for (int j = 0; j <= min(n,q); j++) {
			if (dp[n][j] != 1e9) {
				r = w-1;
				goto skip;
			} 
		}
		l = w+1;
		skip:;
	}
	cout << l << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2752 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15448 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 182 ms 16188 KB Output is correct
4 Correct 14 ms 15448 KB Output is correct
5 Correct 219 ms 16188 KB Output is correct
6 Correct 211 ms 16180 KB Output is correct
7 Correct 8 ms 15452 KB Output is correct
8 Correct 86 ms 15964 KB Output is correct
9 Correct 19 ms 15448 KB Output is correct
10 Correct 15 ms 15448 KB Output is correct
11 Correct 235 ms 16184 KB Output is correct
12 Correct 113 ms 15964 KB Output is correct
13 Correct 8 ms 15448 KB Output is correct
14 Correct 6 ms 15448 KB Output is correct
15 Correct 7 ms 15544 KB Output is correct