Submission #159412

#	Time	Username	Problem	Language	Result	Execution time	Memory
159412		iefnah06	Watching (JOI13_watching)	C++11	100 / 100	108 ms	16252 KiB

watching

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2010;
int N, P, Q;
int A[MAXN];
int dp[MAXN][MAXN];

int nxtSmall[MAXN];
int nxtLarge[MAXN];

bool isGood(int w) {
	for (int i = 0, j = 0; i < N; i++) {
		while (j < N && 0ll + A[i] + w - 1 >= A[j]) j++;
		nxtSmall[i] = j;
	}
	for (int i = 0, j = 0; i < N; i++) {
		while (j < N && 0ll + A[i] + 2*w - 1 >= A[j]) j++;
		nxtLarge[i] = j;
	}

	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int a = 0; a <= P; a++) {
		for (int b = 0; b <= Q; b++) {
			int cur = dp[a][b];
			if (cur == -1) continue;
			if (cur == N) return true;
			dp[a+1][b] = max(dp[a+1][b], nxtSmall[cur]);
			dp[a][b+1] = max(dp[a][b+1], nxtLarge[cur]);
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> P >> Q;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	if (P >= N || Q >= N) {
		cout << 1 << '\n';
		exit(0);
	}

	sort(A, A + N);
	int mi = 0;
	int ma = int(1e9);
	while (ma - mi > 1) {
		int md = (mi + ma) / 2;
		if (isGood(md)) {
			ma = md;
		} else {
			mi = md;
		}
	}
	cout << ma << '\n';

	return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50