oj.uz

Submission #100881

# Submission time Handle Problem Language Result Execution time Memory
100881 2019-03-15T02:07:31 Z square1001 Watching (JOI13_watching) C++14
0 / 100
 169 ms 476 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 476 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Incorrect 169 ms 424 KB Output isn't correct
8 Halted 0 ms 0 KB -