Submission #1239234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239234		quannd	Watching (JOI13_watching)	C++20	100 / 100	148 ms	16152 KiB

watching

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//#define int long long
#define pii pair <ll, ll>
#define fi first
#define se second

const ll N = 2e3 + 5, inf = 2e9, mod = 1e9 + 7, block = 320;

int n, p, q;
int a[N];
int dp[N][N];

void reset() {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= p; j++) dp[i][j] = inf;
	}
	for (int i = 1; i <= p; i++) dp[0][i] = 0;
}
bool check(int mid) {
	reset();
	int small = 0, large = 0;
	for (int i = 1; i <= n; i++) {
		while(a[i] - a[small] + 1 > mid && small < i) {
			small++;
		}
		while(a[i] - a[large] + 1 > 2 * mid && large < i) {
			large++;
		}
		if (small >= 1) small--;
		if (large >= 1) large--;
//		cout << small << ' ' << large << ' ' << i << '\n' << flush;
		for (int j = 0; j <= p; j++) {
//			cout << j << '\n' << flush;
			if (j >= 1) dp[i][j] = min(dp[i][j], dp[small][j - 1]);
			dp[i][j] = min(dp[i][j], dp[large][j] + 1);
		}
	} 
	for (int i = 1; i <= p; i++) {
		if (dp[n][i] <= q) return true;
	}
	return false;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	if (p + q >= n) {
		cout << 1 << '\n';
		return 0;
	}
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	int l = 1, r = 2e9, ans = 0;
//	cout << 1 << '\n' << flush;
	while(l <= r) {
//		cout << l << ' ' << r << '\n' << flush;
		int mid = (l + r) / 2;
		if (check(mid)) {
//			cout << mid << '\n' << flush;
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << '\n';
	return 0;
}

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