Problem:


				Max Score: 350 Points 

Problem Statement

					There are N buildings along the line. The i-th building from the left is colored in color i, and its height is currently a_i meters. 

					Chokudai is a mayor of the city, and he loves colorful thigs. And now he wants to see at least K buildings from the left. 

					You can increase height of buildings, but it costs 1 yens to increase 1 meters. It means you cannot make building that height is not integer. 

					You cannot decrease height of buildings. 

					Calculate the minimum cost of satisfying Chokudai's objective. 

					Note: "Building i can see from the left" means there are no j exists that (height of building j) ≥ (height of building i) and j < i. 

Input Format

N K
a_1 a_2 a_3 ... a_N

Output Format

						Print the minimum cost in one line. In the end put a line break.

Constraints

1 ≤ K ≤ N ≤ 15

1 ≤ a_i ≤ 10^9

Scoring

						Subtask 1 [120 points] 

N = K

						Subtask 2 [90 points] 

N ≤ 5

a_i ≤ 7

						Subtask 3 [140 points] 

There are no additional constraints.

Sample Input 1

5 5
3949 3774 3598 3469 3424

Sample Output 1

1541

					The optimal solution is (height of buildings from the left) = [3949, 3950, 3951, 3952, 3953].

Sample Input 2

5 3
7 4 2 6 4

Sample Output 2

7

					The optimal solution is (height of buildings from the left) = [7, 8, 2, 9, 4].



Sample input:
5 5
3949 3774 3598 3469 3424


Sample output:
1541

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def cost(state):
    now = 0
    ret = 0
    cnt = 0
    for d, a in enumerate(A):
        if (state & (1 << d)) > 0:
            cnt += 1
            ret += max(0, now + 1 - a)
            now = max(now + 1, a)
        else:
            now = max(now, a)

    return ret if cnt >= K else 10**20

ans = 10**20
for state in range(1 << N):
    ans = min(ans, cost(state))

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**20
for i in range(1<<n):
    use = [i>>j&1 for j in range(n)]
    if sum(use) < k:continue
    res=0
    now=a[0]
    for i in range(1,n):
        if now < a[i]:
            now = a[i]
        else:
            if use[i]:
                res += now+1-a[i]
                now += 1

    ans = min(ans,res)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

a = [int(i) for i in input().split()]

ans = float('inf')
for i in range(1 << n):
    res = 0
    cnt = 0
    m = 0
    for j in range(n):
        if i >> j & 1:
            cnt += 1
            res += max(m-a[j] + 1, 0)
            m = max(m+1, a[j])
        else:
            m = max(m, a[j])

    if cnt == k:
        ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
 
N, K = map(int, readline().split())
A = list(map(int, readline().split()))
 
ans = pow(10, 11)
 
for bit in range(1 << (N)):
    if bin(bit).count('1') < K:
        continue
    acc = 0
    pre = 0
    for i in range(N):
        if bit & (1 << i):
            acc += max(0, pre + 1 - A[i])
            pre += 1
        pre = max(pre, A[i])
    ans = min(ans, acc)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

ans = pow(10, 11)

for bit in range(1 << (N)):
    if bin(bit).count('1') < K:
        continue
    acc = 0
    pre = A[0] - 1
    for i, a in enumerate(A[:]):
        if bit & (1 << i):
            if pre < a:
                pre = a
            else:
                acc += pre + 1 - a
                pre = pre + 1
        else:
            if pre < a:
                pre = a

    ans = min(ans, acc)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

ans = pow(10, 11)

for bit in range(1 << (N)):
    if bin(bit).count('1') < K:
        continue
    acc = 0
    pre = 0
    for i in range(N):
        if bit & (1 << i):
            if A[i] <= pre:
                acc += max(0, pre + 1 - A[i])
                pre += 1
        pre = max(pre, A[i])
    ans = min(ans, acc)
print(int(ans))

Submission status: Accepted

Solution code:
# 1<=N<=K<=15
import itertools
N, K = list(map(int, input().split()))
buildings = list(map(int, input().split()))
indexes = [i for i in range(len(buildings))]
building_combinations = [
    combination for combination in itertools.combinations(indexes, K)]

costs = []
for building_combination in building_combinations:
    max_height = 0
    cost = 0
    for i, building in enumerate(buildings):
        if i in building_combination:  # 選んだ建物の場合
            if building <= max_height:
                cost += max_height - building + 1
                max_height = max_height + 1
            else:
                max_height = building
        else:
            if building >= max_height:
                max_height = building
    costs.append(cost)
# print(costs)
print(min(costs))

Submission status: Accepted

Solution code:
import copy
n,k = map(int,input().split())
a = list(map(int,input().split()))

flag = 0
for i in range(2**n):
    state = bin(i)[2:]
    state = '0'*(n - len(state)) + state
    state = [int(i) for i in state]
    
    if sum(state)==k:
        a_state = copy.copy(a)
    
        cost = 0
        for j in range(n):
            if state[j]==1:
                cost_j = max(0,max([0]+a_state[:j])+1-a_state[j])
                cost += cost_j
                a_state[j] += cost_j
            
    
    
        if flag ==0:
            ans =cost
        flag+=1
        ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(x) for x in input().split()]
_min = 1145141919810
for i in range(2**(n-1)):
    ctr = 0
    val = 0
    h_max = a[0]
    for j in range(n-1):
        if (i>>j)&1:
            ctr+=1
            h_max = h_max+1 if h_max>=a[j+1] else a[j+1]
            val+=h_max-a[j+1]
        if h_max<a[j+1]:
            h_max = a[j+1]
    if ctr==k-1 and val<_min:
        _min = val
print(_min)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = float('inf')
for i in range(1<<(n-1)):
    count = 0
    for j in range(n-1):
        if i>>j&1:
            count += 1
    if count < k - 1:
        continue
    minLim = a[0] + 1
    cost = 0
    for j in range(n-1):
        if i>>j&1:
            if a[j+1] < minLim:
                cost += minLim - a[j+1]
                minLim += 1
            else:
                minLim = a[j+1] + 1
        else:
            minLim = max(minLim, a[j+1]+1)
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
def f(i):
    global m
    if i == n:
        if sum(s) == k and s[0] == 1:
            h = [0] * n
            for i in range(n):
                if i == 0:
                    h[0] = a[0]
                    g = 0
                else:
                    if s[i] == 0:
                        if h[g] < a[i]:
                            h[g] = a[i]
                        h[i] = a[i]
                    else:
                        if h[g] >= a[i]:
                            h[i] = h[g] + 1
                        else:
                            h[i] = a[i]
                        g = i
            c = sum(h) - sum(a) 
            if c < m:
                m = c
        return         
    f(i + 1)
    s[i] = 1
    f(i + 1)
    s[i] = 0

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [0 for _ in range(n)]
m = 2 * 10 ** 10
f(0)
print(m)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 一番左はいつも見えている
ans = (10**9)*15
for i in range(2**(n-1)):
    pattern = []
    for j in range(n-1):
        if (i >> j) & 1:
            pattern.append(j+1)
    if len(pattern) != (k-1): continue
    count = 0
    prev = a[0]
    for l in range(1, n):
        if l not in pattern:
            prev = max(prev, a[l])
            continue
        if a[l] <= prev:
            extended = prev + 1
            count += (extended - a[l])
            prev = extended
        else:
            prev = a[l]
    #print(count)
    ans = min(ans, count)
print(0 if k == 1 else ans)

Submission status: Accepted

Solution code:

N,K = map(int,input().split())
a_list = list(map(int,input().split()))

# 建物iをミられる高さにするかいなかのbit探索

ans = 100010001000100010001000

for byte in range(pow(2,N-1)):
    height = a_list[0]
    cost = 0
    if bin(byte).count("1")>=K-1:
        for i in range(N-1):
            if not (byte & 1<<i)==0: # i番目を見る場合
                cost += max(0, height + 1 - a_list[i+1])
                height = max(height + 1, a_list[i+1])
            else:
                height = max(height,a_list[i+1])
        ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    
    ans=10**11
    for bit in range(1<<n):
        s=set()
        for i in range(n):
            if (bit>>i)&1:
                s.add(i)
                
        if len(s)!=k:
          continue       
        
        b=a.copy()
        M=0
        cost=0
        for i in range(n):
            if (i in s) and b[i]<=M:               
                cost+=M-b[i]+1
                b[i]=M+1
                M+=1
            else:
                M=max(M,b[i])
        ans=min(ans,cost)
        
    print(ans)
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# import math
# import bisect
#import numpy as np
import itertools
import copy
import sys

input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int,input().split()))
    a = list(map(int,input().split()))

    cmb = list(itertools.combinations([i for i in range(1, n)], k-1))
    ans = INF

    if k > 1:
            for ele in cmb:
                prc = 0
                prev = a[0]
                acp = copy.copy(a)
                for idx in ele:
                    if acp[idx] - prev <= 0:
                        prc += prev - acp[idx] + 1
                        acp[idx] = prev + 1
                    prev = acp[idx]
                cnt = 1
                mh = acp[0]
                for i in range(1, n):
                    if mh < acp[i]:
                        cnt += 1
                        mh = acp[i]
                if cnt >= k:
                    ans = min(ans, prc)
    else:
        ans = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil
    import copy

    #mod = 1000000007

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    res = 10**17
    for i in range(2**n):
        total, m, cnt = 0, 0, 0
        for j in range(n):
            if(i>>j) & 1:
                cnt += 1
                total += max(m-a[j]+1, 0)
                m = max(m+1, a[j])
            else:
                m = max(m, a[j])
        if cnt == k:
            res = min(res, total)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

inf = 10 ** 19

def main():
    n, k = map(int, input().split())
    num_list = list(map(int, input().split()))

    ans = inf

    for bit in list(product([0, 1], repeat = n)):
        count = bit.count(1)
        if count < k:
            continue
        tmp = 0
        max_hight = 0
        for i in range(n):
            if bit[i] != 1:
                max_hight = max(max_hight, num_list[i])
                continue
            if max_hight >= num_list[i]:
                tmp += max_hight - num_list[i] + 1
                max_hight += 1
            else:
                max_hight = num_list[i]
        ans = min(ans, tmp)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    num_list = list(map(int, input().split()))

    ans = 10**19

    for bit in range(2**n):
        if bin(bit).count('1') != k:
            continue
        tmp = 0
        max_hight = 0
        for i in range(n):
            if bit & (1 << i) == 0:
                if max_hight < num_list[i]:
                    max_hight = num_list[i]
                # max_hight = max(max_hight, num_list[i])
                continue
            if max_hight >= num_list[i]:
                tmp += max_hight - num_list[i] + 1
                max_hight += 1
            else:
                max_hight = num_list[i]
            
        if ans > tmp:
            ans = tmp
        # ans = min(ans, tmp)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 10**19

for bit in range(2**N):
    if bin(bit).count('1') != K:
        continue

    cost, height = 0, 0
    for i in range(N):
        if bit & (1 << i) == 0:
            if height < a[i]:
                height = a[i]
            continue
        if height >= a[i]:
            cost += height - a[i] + 1
            height += 1
        else:
            height = a[i]

    if ans > cost:
        ans = cost

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ans=10**100

for i in range(1<<(n-1)):
    p,q,tmp=1,0,a[0]
    for j in range(n-1):
        if tmp<a[j+1]:
            p+=1
            tmp=a[j+1]
            continue
        if i&(1<<j):
            q+=tmp-a[j+1]+1
            p+=1
            tmp+=1
    if p>=k:
        if ans>q:
            ans=q

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 10**11
for i in range(2**n):
    temp = 0
    b = a[:]
    i = format(i, "0{}b".format(n))
    if i.count("1") == k:
        maxi = 0
        for j in range(n):
            if i[j] == "1":
                if maxi >= b[j]:
                    temp += maxi - b[j] + 1
                    b[j] = maxi + 1
            maxi = max(maxi, b[j])
        ans = min(ans, temp)


print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

# prob1
"""
ans = 0
for i in range(1, len(a)):
    ans += max(a[i-1]-a[i]+1, 0)
    a[i] += max(a[i-1]-a[i]+1, 0)
print(ans)
"""

ans = float("inf")
for i in range(1 << (n - 1)):
    a_copied = a.copy()
    comb = [0]
    cost = 0
    for j in range(n-1):
        if (i >> j) & 1 == 1:
            comb.append(1)
        else:
            comb.append(0)
    if sum(comb) < k - 1:
        continue
    
    for j in range(1, len(comb)):
        if comb[j] == 0:
            continue
        else:
            height = max(0, max(a_copied[:j])-a_copied[j]+1)   
            cost += height
            a_copied[j] += height 
    ans = min(cost, ans)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
ans=10**11
for i in range(2**(n-1)):
  s=format(i,"16b")
  a=0
  for j in range(16):
    if s[j]=="1":
      a=a+1
  if a>=k-1:
    cost=0
    B=[A[0]]
    for j in range(n-1):
      if s[-1-j]!="1":
        B.append(A[j+1])
      else:
        if A[j+1]>max(B):
          B.append(A[j+1])
          continue
        else:
          B.append(max(B)+1)
          cost=cost+max(B)-A[j+1]
    if cost<ans:
      ans=cost
print(ans)

Submission status: Accepted

Solution code:
# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

N, K = map(int, input().split())
original_a = list(map(int, input().split()))

if K == 1:
    print(0)
    exit()

ans = float("inf")
for visible_building_indices in list(itertools.combinations(list(range(N)), K)):
    a = original_a.copy()
    tmp = 0

    for i in range(len(visible_building_indices)):
        try:
            h = max([a[i] for i in range(visible_building_indices[i])])
        except:
            h = 0
        if h >= a[visible_building_indices[i]]:
            tmp += h - a[visible_building_indices[i]] + 1
            a[visible_building_indices[i]] = h + 1

    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
ans=10**18
for i in range(2**n):
  flags=[0]*n
  pos=0
  while i!=0:
    if i%2==1:
      flags[pos]=1
      i-=1
    i=i//2
    pos+=1
  cost=0
  tmp=[0]*n
  tmp[0]=arr[0]
  maxs=arr[0]
  for j in range(1,n):
    if flags[j]==1:
      tmp[j]=max(maxs+1,arr[j])
    else:
      tmp[j]=arr[j]
    cost+=(tmp[j]-arr[j])
    maxs=max(maxs,tmp[j])
  if flags.count(1)>=k:
    ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N, K = map(int, input().split())
a = list(map(int, input().split()))
Min = INF
for i in range(2 ** (N - 1)):
    if bin(i).count("1") == K - 1:
        temp = 0
        M = 0
        for l in range(N - 1):
            if i >> l & 1 == 1:
                if (max(max(a[:l+1]), M) - a[l+1]) < 0:
                    M = a[l+1]
                else:
                    temp += (max(max(a[:l + 2]), M) - a[l + 1]) + 1
                    M = max(max(a[:l + 2]), M) + 1
        if temp < Min:
            Min = temp
print(Min)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split(" "))
a = list(map(int, sys.stdin.readline().split(" ")))

ans = float("inf")
for i in range(2**N):
    pattern = []
    for j in range(N):
        pattern.append(i >> j & 1)
    if sum(pattern) < K:
        continue
    # print(pattern)

    max_h = 0
    tmp_ans = 0
    for n in range(N):
        if pattern[n] == 1:
            if a[n] <= max_h:
                tmp_ans += max_h - a[n] + 1
                max_h += 1
        max_h = max(max_h, a[n])
    ans = min(ans, tmp_ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

#for i in itertools.product([0,1], repeat=n)


n,k=mii()
arr=limii()
ans=10**100
aa=[]
for i in product([0,1], repeat=n):
    if sum(i)==k:

        tmp=0
        chk=0
        for j in range(n):
            if i[j]==1:
                if chk>=arr[j]:
                    tmp+=chk-arr[j]+1
                    chk+=1
                else:
                    chk=arr[j]
            if i[j]==0:
                chk=max(chk,arr[j])
        #print(tmp,i,arr)
        ans=min(tmp,ans)


print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N,K = map(int,input().split())
A = list(map(int,input().split()))
cmin = 10**12
for x in combinations(range(1,N),K-1):
    C = A[:]
    B = [0]
    B += x
    B = sorted(B)
    cnt = 0
    for i in range(1,K):
        j0 = B[i-1]
        j1 = B[i]
        h = 0
        for j in range(j0,j1):
            h = max(h,C[j])
        if C[j1]<=h:
            cnt += h+1-C[j1]
            C[j1] = h+1
    cmin = min(cmin,cnt)
print(cmin)

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline

n, k = map(int,input().split())
a = list(map(int,input().split()))

min_c = 10**11

for i in range(2**n):
    c = 0
    r_a = copy.copy(a)
    bit = 2
    max_a = r_a[0]
    for j in range(1,n):
        if i & bit and r_a[j] <= max_a:
            c += max_a - r_a[j] + 1
            r_a[j] = max_a + 1
        if r_a[j] > max_a:
            max_a = r_a[j]
        bit *= 2
    cl = 1
    max_a = r_a[0]
    for j in range(1,n):
        if r_a[j] > max_a:
            cl += 1
            max_a = r_a[j]
    if cl >= k:
        min_c = min(min_c,c)

print (min_c)

Submission status: Accepted

Solution code:
def ABC106_B():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    ans = 0
    for i in range((N+1)//2):
        cur = i*2+1
        if len(make_divisors(cur))==8:
            ans += 1
    print(ans)
    return

def ABC122_B():
    S = SI()
    ans = 0
    cur = 0
    d = {"A","C","G","T"}
    for s in S:
        if s in d:
            cur += 1
        else:
            ans = max(ans,cur)
            cur = 0
    ans = max(ans,cur)
    print(ans)
    return

def paken2019_C():
    N, M = LI()
    A = [LI()for _ in range(N)]
    T = [i for i in range(M)]
    ans = 0
    for t1,t2 in itertools.permutations(T,2):
        cur = 0
        for i in range(N):
            cur += max(A[i][t1],A[i][t2])
        ans = max(ans,cur)
    print(ans)
    return

def ABC95_C():
    A, B, C, X, Y = LI()
    if A+B<=C*2:
        ans = A*X+B*Y
    else:
        if X>Y:
            ans = Y*C*2 + min(A,C*2)*(X-Y)
        else:
            ans = X*C*2 + min(B,C*2)*(Y-X)
    print(ans)
    return

def SMTB_D():
    def flag(n,s):
        for l in range(n,N):
            if S[l]==str(s):
                return l
        return N
    N = I()
    S = SI()
    ans = 0
    for i in range(10):
        L1 = flag(0,i)
        for j in range(10):
            L2 = flag(L1+1,j)
            for k in range(10):
                L3 = flag(L2+1,k)
                if L3<N:
                    ans += 1
                    #print(i,j,k)
    print(ans)
    return

def JOI2007_3():
    N = I()
    V = [LI() for _ in range(N)]
    D = set()
    for vx,vy in V:
        D.add((vx,vy))
    ans = 0
    for i in range(N):
        a1, b1 = V[i]
        for j in range(i+1,N):
            a2, b2 = V[j]
            va, vb = a2 - a1, b2 - b1
            if (a1 + vb, b1 - va) in D and (a2 + vb, b2 - va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
            if (a1 - vb, b1 + va) in D and (a2 - vb, b2 + va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
    print(ans)
    return
"""
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
"""# 10

def square869120Contest():
    def length(a,b,x,y):
        if x>y:
            x,y = y,x
        rep = 0
        if a<x:
            rep += (x-a)*2
        if y<b:
            rep += (b-y)*2
        rep += (y-x)
        return rep
    N = I()
    AB = [LI()for _ in range(N)]
    ans = inf
    for i in range(N):
        s = AB[i][0]
        for j in range(N):
            g = AB[j][1]
            cur = 0
            for k in range(N):
                cur += length(AB[k][0],AB[k][1],s,g)
            ans = min(ans,cur)
    print(ans)
    return

def JOI7_D():
    M = I()
    S = [LI()for _ in range(M)]
    Ss = [(0,0)]
    curx,cury = S[0]
    for sx,sy in S[1:]:
        Ss.append((sx-curx,sy-cury))
        curx = sx; cury = sy
    #print(Ss)
    N = I()
    X = [LI()for _ in range(N)]
    D = set()
    for i in range(N):
        cur = (X[i][0],X[i][1])
        D.add(cur)
    for i in range(N):
        flag = True
        curx, cury = X[i]
        for k in range(M):
            curx += Ss[k][0]
            cury += Ss[k][1]
            #print(curx,cury)
            if not (curx, cury) in D:
                flag = False
                break
        if flag:
            #print(i,X[i])
            ansx = X[i][0] - S[0][0]
            ansy = X[i][1] - S[0][1]
            print(ansx,ansy)
            return
    return

def ABC128_C():
    N, M = LI()
    S = [[]for _ in range(N)]
    for i in range(M):
        s = LI()
        for j in s[1:]:
            S[j-1].append(i)
    P = LI()
    #print(S)
    loop = 2**N
    ans = 0
    for i in range(loop):
        p = [0]*M
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j)
        for k in cur:
            for l in S[k]:
                p[l] += 1
        flag = True
        for j in range(M):
            if p[j]%2!=P[j]:
                flag = False
        if flag:
            ans += 1
    print(ans)
    return

def ABC2_D():
    N, M = LI()
    V = set()
    for _ in range(M):
        x,y = LI()
        V.add((x,y))
    loop = 2**N
    ans = 0
    #print(V)
    for i in range(loop):
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j+1)
        flag = True
        for k1,k2 in itertools.permutations(cur,2):
            if not ((k1,k2) in V or (k2,k1) in V):
                flag = False
                break
        if flag:
            ans = max(ans,len(cur))
    print(ans)
    return

def JOI7_E():
    R, C = LI()
    A = [LI()for _ in range(R)]
    loop = 2**R
    ans = 0
    for i in range(loop):
        rev = set()
        for j in range(R):
            if (1<<j)&i==(1<<j):
                rev.add(j)
        cur = 0
        for j in range(C):
            s = 0
            for k in range(R):
                if k in rev and A[k][j]==0:
                    s += 1
                elif (not k in rev) and A[k][j]==1:
                    s += 1
            cur += max(s,R-s)
        ans = max(ans,cur)
    print(ans)
    return

def square869120Contest4_B():
    N, K = LI()
    A = LI()
    ans = inf
    loop = 2**(N-1)
    for i in range(loop):
        look = set()
        for j in range(N-1):
            if (1<<j)&i==(1<<j):
                look.add(j+1)
        if len(look)<K-1:
            continue
        high = A[0]
        cur = 0
        flag = True
        for j in range(1,N):
            if not (j in look):
                if A[j]>high:
                    flag = False
                    break
            else:
                if high >= A[j]:
                    cur += (high - A[j] + 1)
                    high += 1
                else:
                    high = A[j]
        #print(look,cur)
        if not flag:
            continue
        ans = min(ans,cur)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    square869120Contest4_B()

"""

"""

Submission status: Accepted

Solution code:
import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 10**11
for obj in itertools.combinations(range(1,N), K-1):
	tmp = A[0]
	cnt = 1
	i = 0
	cost = 0
	for j in range(1,N):
		if j == obj[i]:
			cost += max(0, tmp-A[j]+1)
			tmp = max(tmp+1, A[j])
			i += 1
			cnt += 1
			if cnt == K:
				break
		
		else:
			if A[j] > tmp:
				cnt += 1
				tmp = A[j]

			if cnt == K:
				break

	ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))

ans=10**20
for i in range(2**(N-1)):
    I=i
    T=a[0]
    C=1
    cost=0
    S=[]
    for s in range(N-1):
        if I//(2**(N-2-s))==1:
            S.append("1")
        else:
            S.append("0")
        I%=(2**(N-2-s))
    #print(S)
    for j in range(len(S)):
        if S[j]=="1":
            if a[j+1]>T:
                T=a[j+1]
                C+=1
            else:
                cost+=T+1-a[j+1]
                T+=1
                C+=1
        else:
            if a[j+1]>T:
                T=a[j+1]
                C+=1
    if C>=K and ans>cost:
        ans=cost
    #print(C,cost,S)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

inf = 2 * 10 ** 10

n, k = map(int, input().split())
*a, = map(int, input().split())

ret = inf

for combi in combinations(range(n), r=k):
    set_ = set(combi)

    t = 0
    p = a[0] - 1
    for i, x in enumerate(a):
        if i in set_:
            if p >= x:
                t += p + 1 - x
                p += 1
            else:
                p = x
        else:
            if p < x:
                p = x
    ret = min(ret, t)

print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import product
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    cur_max = A[0]
    count = 1
    for i in range(1,N):
        if cur_max < A[i]:
            cur_max = A[i]
            count += 1
    
    if count >= K:
        print(0)
        return
    answer = 10**11

    for bit in product([0,1],repeat=N):
        cur_max = A[0]
        count = 1
        cost = 0
        for i in range(1,N):
            if cur_max < A[i]:
                cur_max = A[i]
                count += 1
            else:
                if bit[i] == 1:
                    cost += cur_max+1-A[i]
                    cur_max += 1
                    count += 1

        if count >= K:
            answer = min(answer,cost)
    print(answer)


    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))

ans = 10**18

for i in range(2**N):
    count = 0
    maxh = 0
    money = 0
    for j in range(N):
        if i >> j & 1:
            count += 1
            if maxh < A[j]:
                maxh = A[j]
            else:
                money += maxh+1-A[j]
                maxh += 1
        else:
            maxh = max(maxh,A[j])
    if count >= K:
        ans = min(ans,money)

print(ans)