各操作において、\(A_i = x\) である各 \(i\) について \(A_i\) の値を \(0\) に置き換える代わりに \(A_i\) を数列から取り除くことにしても本問題の答えは変わりません。

したがって、数列 \(A\) に含まれる \(x\) の個数を \(c_x\) とすると、\(xc_x\) の値が大きい \(K\) 個の整数 \(x\) に対して操作を行うのが最適であることがわかります。

\(c_x\) の値が正である各 \(x\) について \(c_x\) の値が求められればよいですが、\(x\) の取り得る範囲は \(1\) 以上 \(10^9\) 以下の整数と範囲が広いため、単に配列で管理するのではなく連想配列を用いる、あるいは \(A\) のソート列のランレングス圧縮を計算するなどの工夫が必要です。

時間計算量は \(O(N \log N)\) などになります。入出力例 \(2\) のように \(c_x\) の値が正である \(x\) の個数が \(K\) より少ない場合もあることに注意してください。

実装例

#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';
}