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:
import itertools
N, K = list(map(int, input().split()))
A_orig = list(map(int, input().split()))

res = sum(A_orig)
for pattern in itertools.combinations(range(N), K):
    cnt = 0
    A = A_orig[:]
    for p in pattern:
        if p == 0:
            continue
        extension = max(0, max(A[:p]) - A[p] + 1)
        A[p] += extension
        cnt += extension
    res = min(res, cnt)
print(res)

Submission status: Wrong Answer

Solution code:
def bitcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = float('INF')
for i in range(1<<N):
  if bitcount(i) != K:
    continue
  cost, hights, idx = 0, [], 0
  for j in range(N):
    if j > 0 and i>>j & 1:
      c = max(0, hights[idx] - A[j] + 1)
      cost += c
      hights.append(A[j] + c)
      idx = j
    else:
      hights.append(A[j])
  # print(bin(i), cost, hights)
  r = min(r, cost)
print(r)

Submission status: Wrong Answer

Solution code:
def bitcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = 10**20
for i in range(1<<N):
  if bitcount(i) != K:
    continue
  cost, hights, idx = 0, [], 0
  for j in range(N):
    if j > 0 and i>>j & 1:
      c = max(0, hights[idx] - A[j] + 1)
      cost += c
      hights.append(A[j] + c)
      idx = j
    else:
      hights.append(A[j])
  # print(bin(i), cost, hights)
  r = min(r, cost)
print(r)

Submission status: Wrong Answer

Solution code:
def bitcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = 10**10
for i in range(1<<N):
  if bitcount(i) != K:
    continue
  cost, hights, idx = 0, [], 0
  for j in range(N):
    if j > 0 and i>>j & 1:
      c = max(0, hights[idx] - A[j] + 1)
      cost += c
      hights.append(A[j] + c)
      idx = j
    else:
      hights.append(A[j])
  # print(bin(i), cost, hights)
  r = min(r, cost)
print(r)

Submission status: Wrong Answer

Solution code:
import itertools

n, k = [int(i) for i in input().split()]
now, *a = [int(i) for i in input().split()]

ans = float("inf")
for pp in itertools.product((0, 1), repeat=n-1):
    if sum(pp) < k - 1:
        continue
    cost = 0
    for i, p in enumerate(pp):
        if p == 1:
            if a[i] > now:
                now = a[i]
            else:
                now += 1
                cost += max(now - a[i], 0)
        else:
            if a[i] > now:
                break
    else:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    # 1の数がk未満ならスキップ
    if bin(bit).count("1") < k:
        continue
    # 先頭が1でないならスキップ（先頭は常に見えるため）
    if not bit & 1:
        continue
    # 先頭を今の値にセット
    now = aa[0]
    # このビットにおけるコストを初期化
    cost = 0
    # 2個目からn個目まで進む
    for i in range(1, n):
        # i番目が見える場合
        if bit>>i & 1:
            if aa[i] > now:
                now = aa[i]
            else:
                now = now + 1
                cost += max(now - aa[i], 0)
        # i番目が見えない場合
        else:
            # 見えないはずなのに見えてしまうため、次のビットへ
            if aa[i] > now:
                break

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    # 1の数がk未満ならスキップ
    if bin(bit).count("1") < k:
        continue
    # 先頭が1でないならスキップ（先頭は常に見えるため）
    if not bit & 1:
        continue
    # 先頭を今の値にセット
    now = aa[0]
    # このビットにおけるコストを初期化
    cost = 0
    # 2個目からn個目まで進む
    for i in range(1, n):
        if bit>>i & 1:
            if aa[i] > now:
                now = aa[i]
            else:
                now = now + 1
                cost += now - aa[i]
        else:
            if aa[i] > now:
                break

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    if bin(bit).count("1") < k:
        continue
    if not (bit>>(n-1) & 1):
        continue
    now = aa[0]
    cost = 0
    for i in range(1, n):
        if bit>>i & 1:
            if aa[i] > now:
                now = aa[i]
            else:
                now = now + 1
                cost += now - aa[i]
        else:
            if aa[i] > now:
                break

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    if bin(bit).count("1") < k:
        continue
    if not (bit>>(n-1) & 1):
        continue
    now = aa[0]
    cost = 0
    for i in range(1, n):
        if bit>>i & 1:
            if aa[i] > now:
                now = aa[i]
            else:
                now = now + 1
                cost += now - aa[i]
        else:
            if aa[i] > now:
                continue

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    if bin(bit).count("1") < k:
        continue
    if not (bit & 1):
        continue
    now = aa[0]
    cost = 0
    for i in range(1, n):
        if bit>>i & 1:
            if aa[i] > now:
                now = aa[i]
            else:
                now = now + 1
                cost += now - aa[i]

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
aa = [int(i) for i in input().split()]

ans = float("inf")
for bit in range(1<<n):
    if bin(bit).count("1") < k:
        continue
    if not (bit>>(n-1) & 1):
        continue
    now = aa[0]
    cost = 0
    for i in range(1, n):
        if bit>>i &1:
            cost_i = max(now - aa[i] + 1, 0)
            now = aa[i] + cost_i
            cost += cost_i
    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, k = na()
a = na()
ans = float('inf')
for i in range(2**(n-1)):
    colors = 1
    cost = 0
    tmp = a[0]
    for k in range(n-1):
        if tmp < a[k+1]:
            colors += 1
            tmp = a[k+1]
            continue
        if (i >> k) & 1:
            cost += tmp - a[k+1] + 1
            colors += 1
            tmp += 1
    if colors >= k:
        ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, k = na()
a = na()
ans = float('inf')
for i in range(2**(n-1)):
    tmp = []
    for j in range(n-1):
        if (i >> j) & 1:
            tmp.append(a[j+1])
    nowh = a[0]
    nc = 1
    ct = 0
    for aj in tmp:
        if aj > nowh:
            nowh = aj
            nc += 1
        else:
            ct += nowh - aj + 1
            nc += 1
            nowh += 1
    if nc == k:
        ans = min(ct, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, k = na()
a = na()
ans = 10 ** 17
for i in range(2**(n-1)):
    tmp = []
    for j in range(n-1):
        if (i >> j) & 1:
            tmp.append(a[j+1])
    nowh = a[0]
    nc = 1
    ct = 0
    for aj in tmp:
        if aj > nowh:
            nowh = aj
            nc += 1
        else:
            ct += nowh - aj + 1
            nc += 1
            nowh += 1
    if nc == k:
        ans = min(ct, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, k = na()
a = na()
ans = 10 ** 9
for i in range(2**(n-1)):
    tmp = []
    for j in range(n-1):
        if (i >> j) & 1:
            tmp.append(a[j+1])
    nowh = a[0]
    nc = 1
    ct = 0
    for aj in tmp:
        if aj > nowh:
            nowh = aj
            nc += 1
        else:
            ct += nowh - aj + 1
            nc += 1
            nowh += 1
    if nc == k:
        ans = min(ct, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    ans=INF
    for i in range(2**N):
        c=0
        tmp=0
        l=a[0]
        for j in range(N):
            if j==0:
                if (i>>j)&1:
                    c+=1
                else:
                    break
            else:
                if (i>>j)&1:
                    c+=1
                    tmp+=max(0,l+1-a[j])
                    l=max(l+1,a[j])
        if c>=K:
            ans=min(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    ans=INF
    for i in range(2**N):
        c=0
        tmp=0
        l=a[0]
        for j in range(N):
            if j==0:
                if (i>>j)&1:
                    c+=1
                else:
                    break
            else:
                if (i>>j)&1:
                    c+=1
                    tmp+=max(0,l+1-a[j])
                    l=max(l+1,a[j])
        if c==K:
            ans=min(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(lambda x: x-a[0],a))
    ans=INF
    for i in range(2**(N-1)):
        c=0
        tmp=0
        l=0
        for j in range(N-1):
            if (i>>j)&1:
                c+=1
                if c>K-1:
                    break
                tmp+=max(0,l+1-b[j+1])
                l=max(l+1,b[j+1])
        else:
            if c==K-1:
                ans=min(ans,tmp)
    print(ans if ans!=INF else 0)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(lambda x: x-a[0],a))
    ans=INF
    for i in range(2**(N-1)):
        c=0
        tmp=0
        l=0
        for j in range(N-1):
            if (i>>j)&1:
                c+=1
                if c>K-1:
                    break
                tmp+=max(0,l+1-b[j+1])
                l=max(l+1,b[j+1])
        else:
            if c==K-1:
                ans=min(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
array = list(map(int, input().split()))
if k == 1:
  print(0)
  quit()
  
import itertools
if array[0] < array[1]:
  base = 0
else:
  base = max(0, array[0] - array[1] + 1)
  array[1] = array[0] + 1
  
cost = float('inf')
for cand in itertools.combinations(range(2, n), k-2):
  dp = array[:]
  curr_cost = 0
  for index in cand:
    max_val = max(dp[:index])
    if array[index] > max_val:
      continue
    curr_cost += max_val - array[index] + 1
    dp[index] = max_val + 1
  cost = min(cost, curr_cost)
  
print(base+cost)

Submission status: Wrong Answer

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

import itertools
base = max(0, array[0] - array[1] + 1)
if array[0] < array[1]:
  base = 0
else:
  base = max(0, array[0] - array[1] + 1)
  array[1] = array[0] + 1
cost = float('inf')
for cand in itertools.combinations(range(2, n), k-2):
  dp = array[:]
  curr_cost = 0
  for index in cand:
    max_val = max(dp[:index])
    if array[index] > max_val:
      continue
    curr_cost += max_val - array[index] + 1
    dp[index] = max_val + 1
  cost = min(cost, curr_cost)
  
print(base+cost)

Submission status: Wrong Answer

Solution code:
'''
https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b
解答
https://atcoder.jp/contests/s8pc-4/submissions/2618586
https://atcoder.jp/contests/s8pc-4/submissions/10251329
https://atcoder.jp/contests/s8pc-4/submissions/7015849
'''
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
    if k==1:
        print(0)
        exit()
    
    #WA(last case)
    for i in combinations(range(1, n), k-1):
        i = (0,) + i
        total = 0
        b = a[:]
        for j in range(k-1):
            if b[i[j]]>=b[i[j+1]]:
                total += b[i[j]]-b[i[j+1]]+1
                b[i[j+1]] = b[i[j]]+1
        res = min(res, total)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k= map(int, input().split())
a=list(map(int, input().split()))
b=[0]*n
y=a[0]
for i in range(n):
    y=max(y,a[i])
    b[i]=y




ans=pow(10,12)
for i in range(2**(n-1)):
    H=[]
    for j in range(1,n):
        if (i>>(j-1))&1:
            H.append(j)

    if len(H)==k-1:
        cnt = 0
        x = b[0]
        for l in range(len(H)):
            if x>=b[H[l]]:
                cnt+=x-a[H[l]]+1
                x+=1
            else:
                x=b[l]
        ans=min(cnt,ans)

if k==1:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k= map(int, input().split())
a=list(map(int, input().split()))
b=[0]*n
y=a[0]
for i in range(n):
    y=max(y,a[i])
    b[i]=y



ans=pow(10,12)
for i in range(2**(n-1)):
    H=[]
    for j in range(1,n):
        if (i>>(j-1))&1:
            H.append(j)

    if len(H)==k-1:
        cnt = 0
        x = b[0]
        for l in range(len(H)):
            if x>=b[H[l]]:
                cnt+=x-a[H[l]]+1
                x+=1
            else:
                x=b[l]
        ans=min(cnt,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k= map(int, input().split())
a= list(map(int, input().split()))
b=[]
x=a[0]
count=1
for i in range(1,n):
    if a[i]>x:
        count+=1
        x=a[i]
    else:
        b.append(a[i])




if count>=k:
    print(0)

else:
    b.sort()
    b.reverse()
    ans=0
    for i in range(k-count):
        ans+=x+1-b[i]
        x+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

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

costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        # bit立っている建物の番号のリストを求める
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        # K色の色を見えるようにしたときのcostを求める
        if len(buildings) == K:
            max_height = l_height_copy[0]
            for i in range(1, N):
                if l_height_copy[i] > max_height:
                    max_height = l_height_copy[i]
                if i in buildings:
                    # 建物iの高さを増やす必要があるとき
                    if max_height >= l_height_copy[i]:
                        cost += (max_height + 1) - l_height_copy[i]
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
            costs.append(cost)

print(min(costs))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        # bit立っている建物の番号のリストを求める
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        # K色の色を見えるようにしたときのcostを求める
        if len(buildings) == K:
            # print(f"bits: {bin(bits)}")
            # print(f"buildings: {buildings}")
            max_height = l_height_copy[0]
            for i in range(1, N):
                if l_height_copy[i] > max_height:
                    # print(f"updated max_height: {max_height}")
                    max_height = l_height_copy[i]
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"max_height: {max_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    # 建物iの高さを増やす必要があるとき
                    if max_height >= l_height_copy[i]:
                        # print("max_height >= l_height[i]")
                        cost += (max_height + 1) - l_height_copy[i]
                        # print(f"cost: {cost}")
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
                        # print(f"updated max_height: {max_height}")
            costs.append(cost)

# print(costs)
print(min(costs))

# ----- 方針 -----
# N > Kとする。
# i個目の建物高さを変更するとき1が立つN個のbitsを考える。
# bitが立っている建物の番号のリストを以下で求める。
# buildings = []
# for i in range(N):
#     if bits & (1 << i):
#         buildings.append(i)
# bitsのうち、K個bitが立っているものを考える。
# bitが立っている番号の建物が必ず見えるように高さを増やしたときのcostを求める。

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    prev_height = l_height[0]
    for i in range(1, N):
        if prev_height >= l_height[i]:
            cost += prev_height - l_height[i] + 1
            l_height[i] = prev_height + 1
        prev_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        l_height_copy = l_height[:]
        buildings = []
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)
        cost = 0
        if len(buildings) >= K:
            # print(f"bits: {bin(bits)}")
            # print(f"buildings: {buildings}")
            prev_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"prev_height: {prev_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    if prev_height >= l_height_copy[i]:
                        # print("prev_height >= l_height[i]")
                        cost += prev_height - l_height_copy[i] + 1
                        # print(f"cost: {cost}")
                        l_height_copy[i] = prev_height + 1
                        prev_height = l_height_copy[i]
                        # print(f"updated prev_height: {prev_height}")
                else:
                    if l_height_copy[i] > prev_height:
                        # print(f"updated prev_height: {prev_height}")
                        prev_height = l_height_copy[i]
            costs.append(cost)

# print(costs)
print(min(costs))

# ----- 方針 -----
# N > Kとする。
# i個目の建物高さを変更するとき1が立つN個のbitsを考える。
# bitが立っている建物の番号のリストを以下で求める。
# buildings = []
# for i in range(N):
#     if bits & (1 << i):
#         buildings.append(i)
# bitsのうち、K個bitが立っているものを考える。
# bitが立っている番号の建物が必ず見えるように高さを増やしたときのcostを求める。

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    prev_height = l_height[0]
    for i in range(1, N):
        if prev_height >= l_height[i]:
            cost += prev_height - l_height[i] + 1
            l_height[i] = prev_height + 1
        prev_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        l_height_copy = l_height[:]
        buildings = []
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)
        cost = 0
        if len(buildings) == K:
            # print(f"bits: {bin(bits)}")
            # print(f"buildings: {buildings}")
            prev_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"prev_height: {prev_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    if prev_height >= l_height_copy[i]:
                        # print("prev_height >= l_height[i]")
                        cost += prev_height - l_height_copy[i] + 1
                        # print(f"cost: {cost}")
                        l_height_copy[i] = prev_height + 1
                        prev_height = l_height_copy[i]
                        # print(f"updated prev_height: {prev_height}")
                else:
                    if l_height_copy[i] > prev_height:
                        # print(f"updated prev_height: {prev_height}")
                        prev_height = l_height_copy[i]
            costs.append(cost)

# print(costs)
print(min(costs))

# ----- 方針 -----
# N > Kとする。
# i個目の建物高さを変更するとき1が立つN個のbitsを考える。
# bitが立っている建物の番号のリストを以下で求める。
# buildings = []
# for i in range(N):
#     if bits & (1 << i):
#         buildings.append(i)
# bitsのうち、K個bitが立っているものを考える。
# bitが立っている番号の建物が必ず見えるように高さを増やしたときのcostを求める。
# cost = 0
# prev_height = l_height[0]
# for i in range(1, N):
#     if i in buildings:
#         if prev_height >= l_height[i]:
#             cost += prev_height - l_height[i] + 1
#             l_height[i] = prev_height + 1
#         prev_height = l_height[i]
#     else:
#         if prev_height > l_height[i]:
#             prev_height = l_height[i]

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<n):
        if bin(b).count("1") < k:
            continue
        m = 0
        s = 0
        for i in range(n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] < m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<n):
        if bin(b).count("1") != k:
            continue
        m = 0
        s = 0
        for i in range(n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] < m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import functools 
import sys
import bisect
import string
import math
import time
import random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

N=10**6+2
m=[0]*(N)

n,k=LI()
a=LI()
N=1<<n
ans=inf
for i in range(N):
    c=0
    t=[]
    for j in range(n):
        if (i>>j)&1:
            c+=1
            t+=[j]
    if c!=k:
        continue
    t=t[::-1]
    st=t.pop()
    alt=0
    if st==0:
        p=a[st]
    else:
        p=max(max(a[:st])+1,a[st])
        alt+=max(max(a[:st])+1-a[st],0)
    
    while t:
        h=a[t.pop()]
        alt+=max(0,p+1-h)
        p=p+1
    if alt<ans:
        ans=alt
#        show(ans)

print(ans)