제출 #256833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256833		islingr	구경하기 (JOI13_watching)	C++17	100 / 100	176 ms	16508 KiB

watching

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

const int N = 1 << 11;
int n, P, Q, a[N], dp[N][N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> P >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	if (n <= P) return cout << 1, 0;
	sort(a + 1, a + n + 1);
	int l = 0, r = a[n];
	while (r - l > 1) {
		int w = l + (r - l + 1) / 2;
		for (int i = 1, j = 0, k = 0; i <= n; ++i) {
			while (w <= a[i] - a[j + 1]) ++j;
			while (2 * w <= a[i] - a[k + 1]) ++k;
			dp[i][0] = 1 + dp[k][0];
			for (int p = 1; p <= P; ++p) dp[i][p] = min(dp[j][p - 1], 1 + dp[k][p]);
		}
		(dp[n][P] <= Q ? r : l) = w;
	}
	cout << r;
}

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