제출 #1172873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172873		Tsagana	Watching (JOI13_watching)	C++20	0 / 100	1 ms	324 KiB

watching

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

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

int check(int x) {
	for (int i = 1; i <= q; i++) dp[i][0] = 1e9;
	dp[0][0] = 0;
	int t1 = 1, t2 = 1;
	for (int t3 = 1; t3 <= n; t3++) {
		while (t1 <= t3 && a[t3] - a[t1] >= 2*x) t1++;
		while (t2 <= t3 && a[t3] - a[t2] >= x  ) t2++;
		for (int i = 0; i <= q; i++)  {
			dp[i][t3] = 1e9;
			if (i > 0) dp[i][t3] = min(dp[i-1][t1-1], dp[i][t3]);
			dp[i][t3] = min(dp[i][t2-1] + 1, dp[i][t3]);
		}
	}
	for (int i = 0; i <= q; i++) if (dp[i][n] <= p) return 1;
	return 0;
}
int search(int l, int r, int ans = -1) {
	while (l < r) {
		int m = (l + r) / 2;
		if (check(m)) {ans = m; r = m - 1;}
		else l = m + 1;
	}
	return ans;
}

void solve () {
	cin >> n >> p >> q;
	if (p + q >= n) {cout << 1; return ;}
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	a[0] = -1e9;
	cout << search(1, (a[n] - a[1]) / 2);
}
signed main() {IOS solve(); return 0;}

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