The operation of replacing \(A_i\) with \(0\) for each \(i\) with \(A_i = x\) can be regarded as removing \(A_i\) from the sequence.

Therefore, if we denote by \(c_x\) the number of integers \(x\) contained in the sequence \(A\), it turns out to be optimal to perform the operation for \(K\) integers \(x\) with largest \(xc_x\).

Now the remaining problem is how to manage the value of \(c_x\) for each \(x\) where \(c_x\) is positive. Since \(x\) can range in any integers from \(1\) to \(10^9\), we need a kind of optimization, like using an associative array instead of a simple array, or find the run-length encoded form of the sorted \(A\).

The time complexity is about \(O(N \log N)\). Note that the number of \(x\) where \(c_x\) is positive may be fewer than \(K\), as in Sample Input/Output 2.

Sample code

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

int main() {
	ll n, k;
	cin >> n >> k;
	map<ll, ll> mp;
	for (int i = 0; i < n; i++) {
		ll a;
		cin >> a;
		mp[a]++;
	}
	vector<ll> v;
	for (auto [x, c_x] : mp) v.push_back(x * c_x);
	sort(v.begin(), v.end());
	for (int i = 0; i < k; i++) if (!v.empty()) v.pop_back();
	ll ans = reduce(v.begin(), v.end());
	cout << ans << '\n';
}