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: Wrong Answer

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

# a[1:]で大きさが上位K-1についてフラグを付ける
# フラグがついているのと前回のものの差分＋１をしていく
# この処理をK-1回行った段階で終了させる

target_list = sorted(set(buildings[1:]), reverse=True)[:K-1]

i = 0 #ターゲットリストの添え字
cost = 0
before_building = buildings[0]

for building in buildings[1:]:

    if building in target_list:
        cost += max(before_building - building + 1, 0)
        before_building = building + max(before_building - building + 1, 0)
        # print('building: ', building)
        # print('cost: ', cost)
        # print('before_building: ', before_building)
        i += 1

    if i == K - 1:
        break

print(cost)

Submission status: Wrong Answer

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

# a[1:]で大きさが上位K-1についてフラグを付ける
# フラグがついているのと前回のものの差分＋１をしていく
# この処理をK-1回行った段階で終了させる

target_list = sorted(set(buildings[1:]), reverse=True)[:K-1]

i = 0 #ターゲットリストの添え字
cost = 0
before_building = buildings[0]

for building in buildings[1:]:

    if building in target_list:
        cost += max(before_building - building + 1, 0)
        before_building += 1
        # print('cost: ', cost)
        # print('before_building: ', before_building)
        i += 1

    if i == K - 1:
        break

print(cost)

Submission status: Wrong Answer

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

# a[1:]で大きさが上位K-1についてフラグを付ける
# フラグがついているのと前回のものの差分＋１をしていく
# この処理をK-1回行った段階で終了させる

target_list = sorted(buildings[1:], reverse=True)[:K-1]

i = 0 #ターゲットリストの添え字
cost = 0
before_building = buildings[0]

for building in buildings[1:]:

    if building in target_list:
        cost += max(before_building - building + 1, 0)
        before_building += 1
        # print('cost: ', cost)
        # print('before_building: ', before_building)
        i += 1

    if i == K - 1:
        break

print(cost)

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[]

c=0
for i in range(1,n):
  if a[i-1]<a[i]:
    c+=1
  else:
    break

for i in range(1,k):
  b.insert(0,a[i])

if n>k:
  if c!=0:
    m=min(b[:(-1)*c])
    M=max(b[:(-1)*c])
    for j in range(k,n):
      if a[j]>=M:
        b.insert(0,a[j])
        M=a[j]
        m=min(b[:(-1)*c])
        b.remove(m)
  elif c==0:
    m=min(b)
    M=max(b)
    for j in range(k,n):
      if a[j]>=M:
        b.insert(0,a[j])
        M=a[j]
        m=min(b)
        b.remove(m)

b.append(a[0])
B=list(reversed(b))
p=0
for i in range(1,k):
  if B[i]<=B[i-1]:
    p+=B[i-1]+1-B[i]
    B[i]=B[i-1]+1
print(p)

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[]
for i in range(1,k):
  b.insert(0,a[i])
if n>k:
  m=min(b)
  M=max(b)
  for j in range(k,n):
    if a[j]>=M:
      b.insert(0,a[j])
      M=a[j]
      m=min(b)
      b.remove(m)

b.append(a[0])
B=list(reversed(b))
p=0
for i in range(1,k):
  if B[i]<=B[i-1]:
    p+=B[i-1]+1-B[i]
    B[i]=B[i-1]+1
print(p)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if N == K:
    for i in range(1,N):
        if a[i-1]-a[i]>=0:
            ans += a[i-1]-a[i]+1
            a[i] += a[i-1]-a[i]+1
    print(ans)
    exit(0)

# 最初の状態で見える建物を数える
no_ope = [0]*N
m = 1
highest = a[0]
for i in range(1,N):
    if a[i]>highest:
        m += 1
        highest = a[i]
        no_ope[i] = 1

ans = 10**18
for i in range(1<<N):
    count = 0
    tmp = 0
    for j in range(N):
        if i & (1<<j):
            count += 1
    if count != K: continue
    base_number = 0
    K_idx = []
    for j in range(N):
        if i & (1<<j):
            if no_ope[j]: continue
            K_idx.append(j)
    if len(K_idx) == 0:
        continue
    if K_idx[0] == 0:
        base_number = a[K_idx[0]]
    else:
        base_number = max(a[:K_idx[0]])
    ok = True
    for j in range(len(K_idx)):
        if  base_number+j-a[K_idx[j]] >= 0:
            tmp += base_number+j-a[K_idx[j]]
        else:
            ok = False
            break
    if ok:
        ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if N == K:
    for i in range(1,N):
        if a[i-1]-a[i]>=0:
            ans += a[i-1]-a[i]+1
            a[i] += a[i-1]-a[i]+1
    print(ans)
    exit(0)

ans = 10**18
for i in range(1<<N):
    count = 0
    tmp = 0
    for j in range(N):
        if i & (1<<j):
            count += 1
    if count < K: continue
    base_number = 0
    K_idx = []
    for j in range(N):
        if i & (1<<j):
            K_idx.append(j)
    if len(K_idx) == 0:
        continue
    if K_idx[0] == 0:
        base_number = a[K_idx[0]]
    else:
        base_number = max(a[:K_idx[0]])
    ok = True
    for j in range(len(K_idx)):
        if  base_number+j-a[K_idx[j]] >= 0:
            tmp += base_number+j-a[K_idx[j]]
        else:
            ok = False
            break
    if ok:
        ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**18
for i in range(1<<N):
    count = 0
    tmp = 0
    for j in range(N):
        if i & (1<<j):
            count += 1
    if count < K: continue
    base_number = 0
    K_idx = []
    for j in range(N):
        if i & (1<<j):
            K_idx.append(j)
    if len(K_idx) == 0:
        continue
    if K_idx[0] == 0:
        base_number = a[K_idx[0]]
    else:
        base_number = max(a[:K_idx[0]])
    ok = True
    for j in range(len(K_idx)):
        if  base_number+j-a[K_idx[j]] >= 0:
            tmp += base_number+j-a[K_idx[j]]
        else:
            ok = False
            break
    if ok:
        ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**18
for i in range(1<<N):
    count = 0
    tmp = 0
    for j in range(N):
        if i & (1<<j):
            count += 1
    if count < K: continue
    base_number = 0
    K_idx = []
    for j in range(N):
        if i & (1<<j):
            K_idx.append(j)
    if len(K_idx) == 0:
        continue
    if K_idx[0] == 0:
        base_number = a[K_idx[0]]
    else:
        base_number = max(a[:K_idx[0]])+1
    ok = True
    for j in range(len(K_idx)):
        if  base_number+j-a[K_idx[j]] >= 0:
            tmp += base_number+j-a[K_idx[j]]
        else:
            ok = False
            break
    if ok:
        ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

# best_score = float("inf")
# for sel in combinations(range(N), K):
#     cost = 0

#     # 左からコストを見る
#     # 先頭未満の最大高さを超すまで上げる
#     first = sel[0]
#     first_max = A[first]
#     for k in range(first):
#         first_max = max(first_max, A[k])
#     current = first_max
#     if first_max > 0:
#         cost += abs(A[first] - current) 
    
#     for i in range(1, K):
#         if current > A[sel[i]]:
#             cost += abs(A[sel[i]] - current) + 1
#             current += 1
#         else:
#             current = A[sel[i]] + 1
#     # print(sel, cost)
#     best_score = min(best_score, cost)
# print(best_score)

best_score = float("inf")
for sel in combinations(range(N), K):
    cost = 0

    # selに入っているところだけ変える
    first = sel[0]
    first_max = A[first]
    if first >= 1:
        for k in range(first):
            first_max = max(first_max, A[k])
        cost += abs(current - A[first]) + 1
    else:
        pass
    current = first_max

    for i in range(1, K):
        if current >= A[sel[i]]:
            cost += abs(A[sel[i]] - current) + 1
            current += 1
        else:
            current = A[sel[i]]
    # print(sel, cost)
    best_score = min(best_score, cost)
print(best_score)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

best_score = float("inf")
for sel in combinations(range(N), K):
    cost = 0

    # 左からコストを見る
    # 先頭未満の最大高さを超すまで上げる
    first = sel[0]
    first_max = A[first]
    for k in range(first):
        first_max = max(first_max, A[k])
    current = first_max
    if first_max > 0:
        cost += abs(A[first] - current) 
    
    for i in range(1, K):
        if current > A[sel[i]]:
            cost += abs(A[sel[i]] - current) + 1
            current += 1
        else:
            current = A[sel[i]] + 1
    # print(sel, cost)
    best_score = min(best_score, cost)
print(best_score)

Submission status: Wrong Answer

Solution code:
import copy

n,m = map(int, input().split())
li = list(map(int, input().split()))

ans = 10**18
for i in range(2**n):
    li_copy = copy.copy(li)
    check = [0]*n
    tmp_ans = 0
    
    for j in range(n):
        if ((i >> j) & 1):
            check[n - j - 1] = 1

    if sum(check) < m:
        continue
    
    for x in range(n):
        if x == 0:
            continue
        if check[x] == 0:
            continue
        
        s = max(li_copy[0:x])
        t = li_copy[x]

        if s > t:
            tmp_ans += s - t + 1
            li_copy[x] = s + 1
    ans = min(ans, tmp_ans)
    
print(ans)

Submission status: Wrong Answer

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

ans = 10**12
B = []
for i in range(N):
  B.append(i)
C = list(itertools.combinations(B,K))
#print(len(C))
#print(A[C[0][0]])
D = [0 for i in range(K)]
#print(D[1])

for j in range(len(C)):
  switch = True
  for k in range(K):
    D[k] = A[C[j][k]]
    for l in range(C[j][0]):
    #for l in range(k):
      if D[0] <= A[l]:
        switch = False
      
  if switch == False:
    continue
  
  delta = 0
  #print("-------")
  for i in range(K-1):
    
    if D[i+1] > D[i]:
      continue
    else:
      delta += D[i] - D[i+1] +1
      D[i+1] = D[i]+1
      #print("delta =" + str(delta))
  ans = min(ans, delta)
                 

print(ans)

Submission status: Wrong Answer

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

ans = 10**11
B = []
for i in range(N):
  B.append(i)
C = list(itertools.combinations(B,K))
#print(len(C))
#print(A[C[0][0]])
D = [0 for i in range(K)]
#print(D[1])

for j in range(len(C)):
  switch = True
  for k in range(K):
    D[k] = A[C[j][k]]
    for l in range(C[j][0]):
    #for l in range(k):
      if D[0] <= A[l]:
        switch = False
      
  if switch == False:
    continue
  
  delta = 0
  #print("-------")
  for i in range(K-1):
    
    if D[i+1] > D[i]:
      continue
    else:
      delta += D[i] - D[i+1] +1
      D[i+1] = D[i]+1
      #print("delta =" + str(delta))
  ans = min(ans, delta)
                 

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,K=map(int, input().split())
A=list(map(int, input().split()))
Kcombi=list(itertools.combinations([i for i in range(N)],K))
ans=max(A)*N
tempcost=0
que=[]

for kc in Kcombi:
	for i in sorted(kc):
		que.append(A[i])
		if len(que)>1:
			if que[-2]>=que[-1]:
				tempcost+=que[-2]-que[-1]+1
				que[-1]=que[-2]+1
	#print(kc,que,tempcost)
	if 0 not in kc:	
		if max(A[:min(kc)])>A[min(kc)]:
			ans=min(ans,tempcost+(max(A[:min(kc)])-A[min(kc)])*K)
		else:
			ans=min(ans,tempcost)
	else:
		ans=min(ans,tempcost)
	tempcost=0
	que=[]

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
if m==0:
  print(0)
  exit()
for i in itertools.combinations(range(1,n),m-1):
  s=list(i)
  mx=a[0]
  cost=0
  for j in range(1,n):
    if j in s:
      if a[j]>mx:
        mx=a[j]
        continue
      else:
        cost+=mx+1-a[j]
        mx+=1
    mx=max(mx,a[j])
  ans=min(cost,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for i in itertools.combinations(range(1,n),m-1):
  s=list(i)
  mx=a[0]
  cost=0
  for j in range(1,n):
    if j in s:
      if a[j]>mx:
        mx=a[j]
        continue
      else:
        cost+=mx+1-a[j]
        mx+=1
    mx=max(mx,a[j])
  ans=min(cost,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if height - A[i] < 0:
            cnt += 1
            height = A[i]
        if (b >> i) & 1:
            cnt += 1
            cost += height - A[i] + 1
            height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if height - A[i] < 0:
            #cnt += 1
            height = A[i]
        if (b >> i) & 1:
            cnt += 1
            cost += height - A[i] + 1
            height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if (b >> i) & 1:
            cnt += 1
            if height - A[i] < 0:
                height = A[i]
            else:
                cost += height - A[i] + 1
                height += 1
    if cnt + 1 == K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if (b >> i) & 1:
            cnt += 1
            if height - A[i] < 0:
                height = A[i]
            else:
                cost += height - A[i] + 1
                height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if (b >> i) & 1:
            cnt += 1
            cost += height - A[i] + 1
            height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** N):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N):
        if i == 0:
            continue
        if (b >> i) & 1:
            cnt += 1
            cost += height - A[i] + 1
            height += 1
    if cnt + 1 == K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** (N - 1)):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N - 1):
        if (b >> i) & 1:
            cnt += 1
            cost += height - A[i + 1] + 1
            height += 1
    if cnt + 1 == K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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

import itertools
l=[i for i in range(1,N)]
Arr=list(itertools.combinations(l,K-1)) #Lの中から2個

#print(Arr)

ans=10**12
for i in Arr:
    cost=0
    hight=L[0]
    for j in range(1,N):
        if j in i:
            if hight<L[j]:
                hight=L[j]
            else:
                cost+=(hight-L[j]+1)
                hight+=1
        else:
            hight=max(hight,L[j])
    if ans>cost:
        ans=cost
print(cost)

Submission status: Wrong Answer

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

ans = sum(A[1:])
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            height = max(A[i], height)
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

ans = sum(A)
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            height = max(A[i], height)
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

ans = sum(A)
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

ans = sum(A[1:])
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
for key in range(1 << N):
    if bin(key).count('1') != K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
INF=10**18
a=list(map(int,input().split()))
ans=INF
for i in range(2**(n-1)):
  cst=0
  cnt=0
  b=a[0]
  for j in range(n-1):
    if (i>>j) & 1:
      cst+=max(b+1-a[j+1],0)
      b=max(a[j+1],b+1)
      cnt+=1
    elif a[j+1]>b:
      cst+=a[j+1]-b
      b=a[j]
  if cnt==k-1:
    ans=min(ans,cst)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, k, *a = map(int, open(0).read().split())
ans = 10**9
for i in range(2 << n):
    h = 0
    c = 0
    b = 0
    for j in range(n):
        if a[j] > h:
            b += 1
            h = a[j]
        elif i >> j & 1:
            c += h - a[j] + 1
            h += 1
            b += 1
    if b >= k:
        ans = min(ans, c)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
INF=10**18
a=list(map(int,input().split()))
ans=INF
for i in range(2**(n-1)):
  cst=0
  cnt=0
  b=a[0]
  for j in range(n-1):
    if (i>>j) & 1:
      cst+=max(b+1-a[j+1],0)
      b=max(a[j+1],b+1)
      cnt+=1
    elif a[j]>b:
      cst+=a[j]-b
      b=a[j]
  if cnt==k-1:
    ans=min(ans,cst)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
INF=10**18
a=list(map(int,input().split()))
ans=INF
for i in range(2**(n-1)):
  cst=0
  cnt=0
  b=a[0]
  for j in range(n-1):
    if (i>>j) & 1:
      cst+=max(b+1-a[j+1],0)
      b=max(a[j],b+1)
      cnt+=1
    elif a[j]>b:
      cst+=a[j]-b
      b=a[j]
  if cnt==k-1:
    ans=min(ans,cst)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(n-len(ini_seen)),k-len(ini_seen)):
    sm=0
    work=0
    xtoken=0
    count=1
    for i in range(1,n):
        print(i,work,sm)
        if i in ini_seen:
            count+=1
            if work<ini[i] : work=ini[i]
            else:
                work+=1
                sm+=work-ini[i]
        elif xtoken<len(x) and i==x[xtoken]+count:
            work+=1
            sm+=work-ini[i]
            xtoken+=1
    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(n-len(ini_seen)),k-1):
    sm=0
    work=0
    xtoken=0
    count=1
    for i in range(1,n):
        if i in ini_seen:
            count+=1
            if work<ini[i] : work=ini[i]
            else:
                work+=1
                sm+=work-ini[i]
        elif i==x[xtoken]+count:
            work+=1
            sm+=work-ini[i]
            xtoken+=1
            if xtoken==k-1:break


    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(1,n),k-1):
    token=1
    work=0
    sm=0
    for i in range(k-1):
        while token<len(ini_seen) and x[i]>=ini_seen[token]:
            token+=1
        work+=1
        if work<ini[token-1] : work=ini[token-1]
        sm+=work-ini[x[i]]
    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A_init = list(map(int, input().split()))

    res = f_inf
    for pattern in product([0, 1], repeat=n - 1):
        A = deepcopy(A_init)
        cost = 0
        for idx, p in enumerate(pattern):
            if p == 1:
                prev = max([A[i] for i in range(idx + 1)])
                cost += prev - A[idx + 1] + 1
                A[idx + 1] = prev + 1
        cnt = mi = 0
        for a in A:
            if mi < a:
                mi = a
                cnt += 1
        if cnt >= k:
            res = min(res, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = f_inf
    for pattern in product([0, 1], repeat=n - 1):
        if sum(pattern) < k - 1:
            continue
        cost = 0
        prev = A[0]
        for idx, p in enumerate(pattern):
            if p == 1:
                cost += prev - A[idx + 1] + 1
                prev = prev + 1
        res = min(res, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n, k = map(int, input().split())
ns = list(map(int, input().split()))
res = float('inf')
perms = list(range(1,n))
for p in comb(perms, k-1):
    tmp = ns.copy()
    res_tmp = 0
    res_tmp_add = 0
    p = [0] + list(p)
    for i in range(1,k):
        res_tmp_add = tmp[p[i-1]] - tmp[p[i]]
        if res_tmp_add >= 0:
            tmp[p[i]] += res_tmp_add + 1
            res_tmp += res_tmp_add + 1
    res = min(res, res_tmp)
print(res)

Submission status: Wrong Answer

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

res = float('inf')

for i in range(1<<N):
  a = A[::]
  paint = 0
  cur = None
  add = 0
  for j in range(N):
    if (i>>j)&1:
      paint += 1
      h = a[j]
      if cur is None:
        if j>0 and a[j-1]>=h:
          break
        else:
          cur = h
      else:
        min_h = max(cur, a[j-1])
        if h <= min_h:
          add += (min_h+1) - h
          cur = min_h + 1
          a[j] = cur

  if paint == K:
    res = min(res, add)

print(res)

Submission status: Wrong Answer

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

res = float('inf')

for i in range(1<<N):
  a = A[::]
  paint = 0
  cur = None
  add = 0
  for j in range(N):
    if (i>>j)&1:
      paint += 1
      h = a[j]
      if cur is None:
        if j>0 and a[j-1]>=h:
          break
        else:
          cur = h
      else:
        min_h = max(cur, a[j-1])
        if h < min_h:
          add += (min_h+1) - h
          cur = min_h + 1
          a[j] = cur

  if paint == K:
    res = min(res, add)

print(res)

Submission status: Wrong Answer

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

res = float('inf')

for i in range(1<<N):
  a = A[::]
  paint = 0
  cur = None
  add = 0
  for j in range(N):
    if (i>>j)&1:
      paint += 1
      h = a[j]
      if cur is None:
        if j>0 and a[j-1]>=h:
          break
        else:
          cur = h
      else:
        min_h = max(cur, A[j-1])
        if h < min_h:
          add += (min_h+1) - h
          cur = min_h + 1
          a[j] = cur

  if paint == K:
    res = min(res, add)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

ans = 1 << 60
for x in combinations(range(n), k):
    tmp = arr[list(x)]
    h = 0
    if list(x)[0] != 0:
        small = arr[:list(x)[0]].max() + 1
        if small > tmp[0]:
            h += small - tmp[0]
            tmp[0] += h
    for i in range(1, k):
        if tmp[i - 1] >= tmp[i]:
            h += tmp[i - 1] - tmp[i] + 1
            tmp[i] = tmp[i - 1] + 1
    ans = min(ans, h)

print(ans)

Submission status: Wrong Answer

Solution code:
def num_cleared(N, A):
    cleared = 1
    highest_h = A[0]
    for i in range(1, N):
        h = A[i]
        if h > highest_h:
            cleared += 1
            highest_h = h
    return cleared

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

    cleared = num_cleared(N, A)
    if cleared >= K:
        print(0)
        return

    ans = N * 10**9
    for i in range(1 << N):
        highest_h = A[0]
        cost = 0
        B = [A[0]]
        for j in range(1, N):
            h = A[j]
            if ((i >> j) & 1) == 0:
                highest_h = max(h, highest_h)
                B.append(h)
                continue
            if highest_h >= h:
                cost += (highest_h - h) + 1
                highest_h += 1
                B.append(highest_h + 1)
            else:
                B.append(h)
        cleared = num_cleared(N, B)
        if cleared >= K:
            ans = min(ans, cost)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def num_bits(n):
    ans = 0
    while n > 0:
        ans += (n & 1)
        n >>= 1
    return ans

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = N * 10**9
    for i in range(1 << (N - 1)):
        nbits = num_bits(i)
        if nbits != K - 1:
            continue
        last_h = A[0]
        cost = 0
        for j in range(N - 1):
            if ((i >> j) & 1) != 1:
                continue
            h = A[j + 1]
            if last_h >= h:
                cost += (last_h - h) + 1
                last_h += 1
            else:
                hast_h = h
        ans = min(cost, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def num_bits(n):
    ans = 0
    while n > 0:
        ans += (n & 1)
        n >>= 1
    return ans

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = N * 10**9
    for i in range(1 << (N - 1)):
        nbits = num_bits(i)
        if nbits != K - 1:
            continue
        last_h = A[0]
        cost = 0
        for j in range(N - 1):
            if ((i >> j) & 1) != 1:
                continue
            h = A[j + 1]
            if last_h >= h:
                cost += (last_h - h) + 1
                last_h += 1
        ans = min(cost, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(2**(N-1)):
    limit=A[0]
    L=[0]*(N-1)
    total=0
    count=0
    for j in range(N-1):
        if ((i>>j)&1):
            L[j]=1
            count+=1
    if count>=K-1:
        for m in range(N-1):
            if L[m]==1:
                height=max(max(A[:m+1])+1,A[m+1])
                total+=height-A[m+1]
                A[m+1]=height
        ans.append(total)

print(min(ans))