제출 #976111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976111		vjudge1	구경하기 (JOI13_watching)	C++17	0 / 100	37 ms	348 KiB

watching

/*

*/

#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) {
		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
• Subtask 2: 0 / 50