oj.uz

Submission #464322

# Submission time Handle Problem Language Result Execution time Memory
464322 2021-08-12T23:34:22 Z Hamed5001 Watching (JOI13_watching) C++14
0 / 100
 76 ms 408 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 2e3+10;
ll A[mxN], N, P, Q;

bool ok(ll mid) {
	vector<bool> covered(N, 0);
	
	int PP = P, QQ = Q;
	while(QQ--) {
		bool done = 1;
		int idx = -1, val = 0;
		for (int i = 0; i < N; i++) {
			int cnt = 0;
			if (!covered[i]) {
				int ii = i;
				while(ii < N && A[ii] < A[i] + 2 * mid) {
					cnt+=!covered[ii++];
				}
				if (cnt > val) {
					val = cnt;
					idx = i;
				}
				done = 0;
			}
		}
		if (done) break;
		for (int i = idx; i < idx + val; i++)
			covered[i] = 1;
	}


	for (int i = 0; i < N; i++) {
		if (!covered[i]) {
			PP--;
			int ii = i;
			while(ii < N && A[ii] < A[i] + mid)
				covered[ii++] = 1;
		}
	}
	return PP >= 0;
}

void solve() {
	cin >> N >> P >> Q;
	set<int> st;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		st.insert(x);
	}

	int i = 0;
	for (auto it : st) {
		A[i++] = it;
	}
	N = st.size();

	ll l = 1, r = 1e10, mid;
	while(l < r) {
		mid = (l+r) >> 1;
		if (ok(mid)) r = mid;
		else l = mid+1;
	}
	cout << r << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 408 KB Output isn't correct
2 Halted 0 ms 0 KB -