oj.uz

답안 #464321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464321 2021-08-12T22:51:09 Z Hamed5001 구경하기 (JOI13_watching) C++14
0 / 100
 3 ms 332 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) {
	priority_queue<pair<int, int>> pq;
	vector<bool> covered(N+10, 0);
	for (int i = 0; i < N; i++) {
		int can = lower_bound(A+i, A+N, A[i] + mid*2) - (A+i);
		// cerr << i << ' ' << can << ' ' << mid << endl;
		pq.push({can, i});
	} 
	int PP = P, QQ = Q;
	while(QQ && !pq.empty()) {
		if (!covered[pq.top().second]) {
			for (int i = pq.top().second; i < pq.top().second+pq.top().first; i++)
				covered[i] = 1;
			QQ--;
		}
		pq.pop();
	}

	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;
	for (int i = 0; i < N; i++)
		cin >> A[i];

	sort(A, A+N);

	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -