Submission #1279002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279002		IBory	구경하기 (JOI13_watching)	C++20	100 / 100	211 ms	16176 KiB

watching

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

const int MAX = 2004;
int A[MAX], dp[MAX][MAX], pv[2][MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, P, Q;
	cin >> N >> P >> Q;
	P = min(P, N); Q = min(Q, N);
	for (int i = 1; i <= N; ++i) cin >> A[i];
	sort(A + 1, A + N + 1);

	ll l = 0, r = (ll)1e9 + 1;
	while (l + 1 < r) {
		ll mid = (l + r) >> 1;
		for (int i = 1; i <= N; ++i) {
			pv[0][i] = (upper_bound(A + 1, A + N + 1, A[i] - mid) - A) - 1;
			pv[1][i] = (upper_bound(A + 1, A + N + 1, A[i] - 2LL * mid) - A) - 1;
		}

		memset(dp, 0x3f, sizeof(dp));
		for (int q = 0; q <= Q; ++q) {
			dp[q][0] = 0;
			for (int i = 1; i <= N; ++i) {
				if (q) dp[q][i] = dp[q - 1][pv[1][i]];
				dp[q][i] = min(dp[q][i], dp[q][pv[0][i]] + 1);
			}
		}
		(dp[Q][N] <= P ? r : l) = mid;
	}

	cout << r;
	return 0;
}

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