oj.uz

Submission #100882

# Submission time Handle Problem Language Result Execution time Memory
100882 2019-03-15T02:11:12 Z square1001 Watching (JOI13_watching) C++14
100 / 100
 252 ms 4360 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) {
			watchp[i] = (i >= 1 ? watchp[i - 1] : 0);
			watchq[i] = (i >= 1 ? watchq[i - 1] : 0);
			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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 252 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 2 ms 412 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 25 ms 808 KB Output is correct
9 Correct 26 ms 828 KB Output is correct
10 Correct 44 ms 1124 KB Output is correct
11 Correct 41 ms 1176 KB Output is correct
12 Correct 252 ms 4360 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct