fork(1) download
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. int n, m, popcount[32777]; long long a[19];
  6. int main() {
  7. cin >> n >> m;
  8. for (int i = 0; i < n; i++) cin >> a[i];
  9. long long ret = 1LL << 60;
  10. for (int i = 0; i < 1 << n; i++) {
  11. popcount[i] = popcount[i >> 1] + (i & 1);
  12. if (i % 2 == 0 || popcount[i] < m) continue;
  13. vector<int> b;
  14. for (int j = 0; j < n; j++) {
  15. if (i & (1 << j)) b.push_back(j);
  16. }
  17. b.push_back(n);
  18. long long sum = 0, l = 0;
  19. for (int j = 0; j < b.size() - 1; j++) {
  20. l = max(l + 1, *max_element(a + b[j], a + b[j + 1]));
  21. sum += l - a[b[j]];
  22. }
  23. ret = min(ret, sum);
  24. }
  25. cout << ret << endl;
  26. return 0;
  27. }
Success #stdin #stdout 0s 15368KB
stdin
5 5
3949 3774 3598 3469 3424
stdout
1541