Submission #485352

#	Time	Username	Problem	Language	Result	Execution time	Memory
485352		zhougz	Watching (JOI13_watching)	C++17	100 / 100	160 ms	8516 KiB

watching

/**
 *    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 / 50
• Subtask 2: 50 / 50