Submission #100881

#	Time	Username	Problem	Language	Result	Execution time	Memory
100881		square1001	Watching (JOI13_watching)	C++14	0 / 100	169 ms	476 KiB

watching

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, P, Q;
	cin >> N >> P >> Q;
	vector<int> A(N);
	for(int i = 0; i < N; ++i) cin >> A[i];
	sort(A.begin(), A.end());
	if(P + Q >= N) {
		cout << 1 << endl;
		return 0;
	}
	int L = 0, R = (1 << 30) - 17;
	while(R - L > 1) {
		int M = (L + R) >> 1;
		vector<int> watchp(N + 1), watchq(N + 1);
		for(int i = 0; i <= N; ++i) {
			while(watchp[i] != N && A[watchp[i]] - A[i] < M) ++watchp[i];
			while(watchq[i] != N && A[watchq[i]] - A[i] < 2 * M) ++watchq[i];
		}
		vector<vector<int> > dp(P + 1, vector<int>(Q + 1, 0));
		for(int i = 0; i <= P; ++i) {
			for(int j = 0; j <= Q; ++j) {
				if(i >= 1) dp[i][j] = max(dp[i][j], watchp[dp[i - 1][j]]);
				if(j >= 1) dp[i][j] = max(dp[i][j], watchq[dp[i][j - 1]]);
			}
		}
		if(dp[P][Q] == N) R = M;
		else L = M;
	}
	cout << R << endl;
	return 0;
}

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