oj.uz

Submission #485352

# Submission time Handle Problem Language Result Execution time Memory
485352 2021-11-07T08:24:00 Z zhougz Watching (JOI13_watching) C++17
100 / 100
 160 ms 8516 KB 
/**
 *    author: chowgz
 *    created: 07/11/2021 15:53:01
**/
#include <bits/stdc++.h>

using namespace std;

int n, p, q;
const int MAXN = 2'000;
int arr[MAXN + 5];
int dp[MAXN + 5][MAXN + 5];
// I looked at the solution. Let dp[i][j] store index covered with
// i short and j long left.
int nxt1[MAXN + 5], nxt2[MAXN + 5];

bool bs(int x) {
	for (int i = 0; i < n; i++) {
		nxt1[i] = upper_bound(arr, arr + n, arr[i] + x - 1) - arr;
		nxt2[i] = upper_bound(arr, arr + n, arr[i] + 2 * x - 1) - arr;
	}
	nxt1[n] = n;
	nxt2[n] = n;
	for (int i = p; i >= 0; i--) {
		for (int j = q; j >= 0; j--) {
			if (i == p) {
				if (j == q) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = nxt2[dp[i][j + 1]];
				}
			} else {
				if (j == q) {
					dp[i][j] = nxt1[dp[i + 1][j]];
				} else {
					dp[i][j] = max(nxt1[dp[i + 1][j]], nxt2[dp[i][j + 1]]);
				}
			}
			
		}
	}
	return dp[0][0] == n;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	if (p + q >= n) {
		cout << 1 << '\n';
		return 0;
	}
	sort(arr, arr + n);
	int l = 1, r = 1'000'000'000, m;
	while (l != r) {
		m = (l + r) / 2;
		if (bs(m)) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	cout << l << '\n';
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 268 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 19 ms 1200 KB Output is correct
9 Correct 20 ms 3756 KB Output is correct
10 Correct 33 ms 8516 KB Output is correct
11 Correct 31 ms 968 KB Output is correct
12 Correct 160 ms 8132 KB Output is correct
13 Correct 5 ms 332 KB Output is correct
14 Correct 5 ms 332 KB Output is correct
15 Correct 6 ms 332 KB Output is correct