Submission #1214057

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, K;
  cin >> N >> K;
  vint a(N);
  rep(i, N) cin >> a[i];
  int ans = inf;
  rep(bit, 1<<N) {
    if(__builtin_popcount(bit) != K) continue;
    int sum = 0;
    int mx = 0;
    rep(i, N) {
      if((bit>>i)&1) {
	if(a[i] <= mx) {
	  mx++;
	  sum += mx-a[i];
	}
      }
      chmax(mx, a[i]);
    }
    chmin(ans, sum);
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result