Backup

input/code.cpp: In function 'int main()':
input/code.cpp:56:21: warning: unused variable 'nlen' [-Wunused-variable]
       auto [nx, nlen] = *next(it);
                     ^
input/code.cpp:62:21: warning: unused variable 'plen' [-Wunused-variable]
       auto [px, plen] = *prev(it);
                     ^
input/code.cpp:41:19: warning: unused variable 'ix' [-Wunused-variable]
     auto [ix, ilen] = *it;
                   ^

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct T {
  static const int N = 1 << 18;
  pair<int, int> p[N * 2];
  T() {
    fill(p, p + N * 2, pair{INF, INF});
  }
  void change(int k, int x) {
    p[k + N] = {x, k};
    k += N;
    while (k != 1) {
      k /= 2;
      p[k] = min(p[k * 2], p[k * 2 + 1]);
    }
  }
  int operator()() { return p[1].second; }
  int operator[](int i) { return p[i + N].first; }
};
int main() {
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a, a + n);
  n -= 1;
  T t;
  set<pair<int, int>> act;
  for (int i = 0; i < n; ++i) {
    t.change(i, a[i + 1] - a[i]);
    act.emplace(i, 1);
  }
  int r = 0;
  while (k--) {
    int i = t();
    r += t[i];
    auto it = act.lower_bound(pair{i, 0});
    auto [ix, ilen] = *it;
    bool hp = it != act.begin() && prev(it)->first + prev(it)->second == i;
    bool hn = next(it) != act.end() && i + ilen == next(it)->first;
    if (hp && hn) {
      auto [px, plen] = *prev(it);
      auto [nx, nlen] = *next(it);
      act.erase(prev(it));
      act.erase(next(it));
      act.erase(it);
      int c = t[px] + t[nx] - t[i];
      t.change(i, INF);
      t.change(nx, INF);
      t.change(px, c);
      act.emplace(px, plen + ilen + nlen);
    } else if (hn) {
      auto [nx, nlen] = *next(it);
      act.erase(next(it));
      act.erase(it);
      t.change(i, INF);
      t.change(nx, INF);
    } else if (hp) {
      auto [px, plen] = *prev(it);
      act.erase(prev(it));
      act.erase(it);
      t.change(i, INF);
      t.change(px, INF);
    }
  }
  cout << r << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 2, 3

Verdict: ACCEPTED

Test 19

Group: 2, 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED