Submission #9180775

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 100;

ll n, m, v, p, ans, a[N], ps[N];

bool ok(int dex) {
	vector<int> vec;
	for (int i = 0; i < n; i++)
		if (i != dex)
			vec.push_back(a[i]);
	ll x = a[dex] + m;
	int cnt = 0;
	for (int y: vec)
		if (y > x)
			cnt++;
	if (cnt >= p)
		return false;
	for (int i = 0; i < p - 1; i++)
		vec.pop_back();
	ll res = 0;
	for (int y: vec)
		res += min(m, x - y);
	return res >= m * (v - p);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> v >> p;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i++)
		ps[i + 1] = ps[i] + a[i];
	int l = -1, r = n - 1;
	while (r - l > 1) {
		int c = (l + r) >> 1;
		if (ok(c))
			r = c;
		else
			l = c;
	}
	cout << n - r;
}

Submission Info

Judge Result