제출 #1239227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239227		wedonttalkanymore	구경하기 (JOI13_watching)	C++20	0 / 100	2 ms	392 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, P = 1e5 + 5, inf = 2e9, mod = 1e9 + 7, block = 320;

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

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) {
	vector <vector <int> > dp;
	dp.assign(n + 1, vector <int> (p + 1, inf));
	for (int i = 1; i <= p; i++) dp[0][i] = 0;
//	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;
	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: 0 / 50
• Subtask 2: 0 / 50