Submission #100874

#	Time	Username	Problem	Language	Result	Execution time	Memory
100874		E869120	Watching (JOI13_watching)	C++14	100 / 100	197 ms	8716 KiB

watching

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

long long N, A[2009]; int P, Q;
int dp[2009][2009];
int P1[2009], P2[2009];

bool solve(long long uplim) {
	for (int i = 0; i <= N; i++) P1[i] = lower_bound(A, A + N, A[i] + uplim) - A;
	for (int i = 0; i <= N; i++) P2[i] = lower_bound(A, A + N, A[i] + 2LL * uplim) - A;
	
	for (int i = 0; i <= P; i++) { for (int j = 0; j <= Q; j++) dp[i][j] = 0; }
	
	for (int i = 0; i <= P; i++) {
		for (int j = 0; j <= Q; j++) {
			dp[i][j + 1] = max(dp[i][j + 1], P2[dp[i][j]]);
			dp[i + 1][j] = max(dp[i + 1][j], P1[dp[i][j]]);
		}
	}
	if (dp[P][Q] == N) return true;
	return false;
}

int main(){
	cin >> N >> P >> Q; if (Q >= N) Q = N; if (P + Q >= N) P = N - Q;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);
	A[N] = 1000000007;
	
	long long L = 1, R = 1000000007, M, maxn = (1 << 30);
	for (int i = 0; i < 35; i++) {
		M = (L + R) / 2;
		bool ok = solve(M);
		if (ok == true) { R = M; maxn = min(maxn, M); }
		else { L = M; }
	}
	cout << maxn << endl;
	return 0;
}

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