oj.uz

Submission #976092

# Submission time Handle Problem Language Result Execution time Memory
976092 2024-05-06T07:30:29 Z vjudge1 Watching (JOI13_watching) C++17
0 / 100
 33 ms 348 KB 
/*

*/

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

#define int long long

const int inf = 2e9;

int n, p, q, k;
vector<int> a, nxt1, nxt2;
vector<vector<int>> dp;

int f(int i, int b) {
	if (i == n) {
		return 0;
	}
	if (dp[i][b] != -1) {
		return dp[i][b];
	}
	int ret = f(nxt1[i], b) + 1;
	if (b > 0) ret = min(ret, f(nxt2[i], b - 1));
	return dp[i][b] = ret;
}

signed main() {
	cin >> n >> p >> q;

	a.resize(n);
	nxt1.resize(n);
	nxt2.resize(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a.begin(), a.end());

	if (p + q >= n) {
		cout << 1 << '\n';
		return 0;
	}

	int lo = 1, hi = 1e9, ans = 1e9;
	while (lo <= hi) {
		int k = (lo + hi) >> 1;

		for (int i = 0; i < n; i++) {
			bool ok = 0;
			for (int j = i + 1; j < n; j++) {
				if (a[j] > a[i] + k) {
					nxt1[i] = j, ok = 1;
					break;
				} 
			}
			if (!ok) {
				nxt1[i] = n;
			}
			ok = 0;
			for (int j = i + 1; j < n; j++) {
				if (a[j] > a[i] + 2 * k) {
					nxt2[i] = j, ok = 1;
					break;
				} 
			}
			if (!ok) {
				nxt2[i] = n;
			}
		}

		dp.assign(n, vector<int>(q + 1, -1));

		if (f(0, q) <= p) {
			hi = k - 1, ans = k;
		} else {
			lo = k + 1;
		}
	}

	cout << ans << '\n';
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -