fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long MOD = 1000000007;
  4. void init_code() {
  5. #ifndef ONLINE_JUDGE
  6.     freopen("input.txt", "r", stdin);
  7.     freopen("output.txt", "w", stdout);
  8. #endif
  9. }
  10. int main() {
  11.     init_code();
  12.     long long t;
  13.     cin >> t;
  14.     while (t--) {
  15.         long long n, k;
  16.         cin >> n >> k;
  17.         vector<long long> a(n);
  18.         vector<long long> hold;
  19.         map<long long, long long> check;
  20.         for (long long i = 0; i < n; i++) {
  21.             cin >> a[i];
  22.             check[a[i]]++;
  23.         }
  24.         for (auto it : check) {
  25.             hold.push_back(it.second);
  26.         }
  27.         sort(hold.begin(), hold.end());
  28.         for (long long i = hold.size() - 1; i >= 0 && k > 0; i--) {
  29.             if (k >= hold[i] - 1) {
  30.                 k -= (hold[i] - 1);
  31.                 hold[i] = 1;
  32.             } else {
  33.                 hold[i] -= k;
  34.                 k = 0;
  35.             }
  36.         }
  37.         long long ans = (n * (n - 1)) / 2;
  38.         for (size_t i = 0; i < hold.size(); i++) {
  39.             if (hold[i] > 1) {
  40.                 ans -= (hold[i] * (hold[i] - 1)) / 2;
  41.             }
  42.         }
  43.         cout << ans << "\n";
  44.     }
  45.     return 0;
  46. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
1
5 2
1 2 3 4 5
stdout
copy 
10
https://ideone.com/89TSgB
language:
C++ (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!