oj.uz

Submission #159415

# Submission time Handle Problem Language Result Execution time Memory
159415 2019-10-22T16:04:26 Z iefnah06 Watching (JOI13_watching) C++11
0 / 100
 70 ms 16248 KB 
#include<bits/stdc++.h>
using namespace std;

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

int dp[MAXN][MAXN];
int nxtLarge[MAXN];
int nxtSmall[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::sync_with_stdio(0), cin.tie(0);
	cin >> N >> P >> Q;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	if (P >= N || Q >= N) {
		cout << -1 << '\n';
		exit(0);
	}

	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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16120 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16248 KB Output is correct
2 Correct 41 ms 16236 KB Output is correct
3 Correct 70 ms 16124 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -