oj.uz

Submission #485351

# Submission time Handle Problem Language Result Execution time Memory
485351 2021-11-07T08:22:40 Z zhougz Watching (JOI13_watching) C++17
0 / 100
 371 ms 12100 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];
	}
	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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 371 ms 12100 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -