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 sys

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

    if N == K:
        mask = [1] * N

        print(calc(N, a, mask))
        return

    ans = sys.maxsize
    for i in range(1 << N):
        if i % 2 == 0:continue
        mask = [i >> j & 1 for j in range(N)]
        if sum(mask) < K: continue
        mask.reverse()

        ans = min(ans, calc(N, a, mask))

    print(ans)
    return

def calc(N, a, mask):
    ans = 0
    m = a[0]
    for i in range(1, N):
        m = max(m, a[i - 1])
        if mask[i] == 0:continue
        if m < a[i]:
            continue
        else:
            v = m - a[i] + 1
            ans += v
            m = a[i] + v

    return ans

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

    if N == K:
        mask = [1] * N

        print(calc(N, a, mask))
        return

    ans = sys.maxsize
    for i in range(1 << N):
        if i % 2 == 0:continue
        mask = [i >> j & 1 for j in range(N)]
        if sum(mask) != K: continue
        mask.reverse()

        ans = min(ans, calc(N, a, mask))

    print(ans)
    return

def calc(N, a, mask):
    ans = 0
    m = a[0]
    for i in range(1, N):
        m = max(m, a[i - 1])
        if mask[i] == 0:continue
        if m < a[i]:
            continue
        else:
            v = m - a[i] + 1
            ans += v
            m = a[i] + v

    return ans

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    if N == K:
        mask = [1] * N

        print(calc(N, a, mask))
        return

    ans = 10 ** 12
    for i in range(1 << N):
        if i % 2 == 0:continue
        mask = [i >> j & 1 for j in range(N)]
        if sum(mask) != K: continue
        mask.reverse()

        ans = min(ans, calc(N, a, mask))

    print(ans)
    return

def calc(N, a, mask):
    ans = 0
    m = a[0]
    for i in range(1, N):
        m = max(m, a[i - 1])
        if mask[i] == 0:continue
        if m < a[i]:
            continue
        else:
            v = m - a[i] + 1
            ans += v
            m = a[i] + v

    return ans

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mask = [0] * N

if N == K:
    mask = [1] * N

ans = 0
m = a[0]
for i in range(1, N):
    if mask[i] == 0:continue
    m = max(m, a[i - 1])
    if m < a[i]:
        continue
    else:
        v = m - a[i] + 1
        ans += v
        m = a[i] + v

print(ans)

Submission status: Wrong Answer

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

temp = "0" + str(N) + "b"
case = []
for i in range(2 ** N):
    x = format(i, temp)
    if x[0] == "1" and x.count("1") >= K:
        case.append(x)

result = []
for x in case:
    test = heights.copy()
    now = test[0]
    for y in range(1, N):
        if x[y] == "1":
            if test[y] <= now:
                test[y] = now + 1
                now = test[y]
            else:
                now = test[y]
    result.append(test)

ans=float('inf')
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[j]
    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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

temp = "0" + str(N) + "b"
case = []
for i in range(2 ** N):
    x = format(i, temp)
    if x[0] == "1" and x.count("1") >= K:
        case.append(x)

result = []
for x in case:
    test = heights.copy()
    now = test[0]
    for y in range(1, N):
        if x[y] == "1":
            if test[y] <= now:
                test[y] = now + 1
                now = test[y]
            else:
                now = test[y]
    result.append(test)

ans = 100000000000000
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[j]
    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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

temp = "0" + str(N) + "b"
case = []
for i in range(2 ** N):
    x = format(i, temp)
    if x[0] == "1" and x.count("1") >= K:
        case.append(x)

result = []
for x in case:
    test = heights.copy()
    now = test[0]
    for y in range(1, N):
        if x[y] == "1":
            test[y] = now + 1
            now = test[y]
    result.append(test)

ans = 100000000000000
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[j]
    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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

temp = "0" + str(N) + "b"
case = []
for i in range(2 ** N):
    x = format(i, temp)
    if x[0] == "1" and x.count("1") >= K:
        case.append(x)

result = []
for x in case:
    test = heights.copy()
    now = test[0]
    for y in range(1, N):
        if x[y] == "1":
            test[y] = now + 1
            now = test[y]
    result.append(test)

ans = 1000000000000
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[j]
    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=10**12
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      x=a[j+1]
      cnt+=1
      if x>=t:
        t=x+1
      else:
        s+=(t-x)
        t+=1
  if cnt>=K-1:
    ans=min(s,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      x=a[j+1]
      cnt+=1
      if x>=t:
        t=x+1
      else:
        s+=(t-x)
        t+=1
    else:
      t=max(t,a[j+1]+1)
  if cnt>=K-1:
    ans=min(s,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      x=a[j+1]
      cnt+=1
      if x>=t:
        t=x+1
      else:
        s+=(t-x)
        t+=1
  if cnt>=K-1:
    ans=min(s,ans)
print(ans)

Submission status: Wrong Answer

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

ans = max(a) * N

for i in range(pow(2, N)):
    candidate = bin(i)[2:].zfill(N)
    if candidate.count("1") != K:
        continue

    cost = 0
    local_min = a[0] - 1
    for j, build in enumerate(a):
        if candidate[j] == "1":
            cost += max(0, local_min + 1 - build)
            local_min = max(build, local_min + 1)

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    print("bit",bit)
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]!=max(a[:i+1]):
                sm+=max(a[:i+1])-a[i]+1
                a[i]=max(a[:i+1])+1
    cnt=1
    for i in range(1,N):
        if max(a[:i])<a[i]:
            cnt+=1
    if cnt==K:
        ans=min(ans,sm)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]!=max(a[:i+1]):
                sm+=max(a[:i+1])-a[i]+1
                a[i]=max(a[:i+1])+1
    cnt=1
    for i in range(1,N):
        if max(a[:i])<a[i]:
            cnt+=1
        if cnt==K:
            ans=min(ans,sm)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]!=max(a[:i+1]):
                sm+=max(a[:i+1])-a[i]+1
                a[i]=max(a[:i+1])+1
    if c[1:].count(1)==K-1:
        ans=min(ans,sm)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
N,K = map(int,input().split())
A_list = list(map(int,input().split()))	
###########
can_see = [0]
for i in range(0,N-1):
  max_building = A_list[0]
  if max_building < A_list[i+1]:
    can_see.append(i+1)
    max_building = A_list[i+1]

#print("can_see",can_see)
need_to_build = K-len(can_see)
#print("NTB",need_to_build)

#1つ目のタワーは足すことがないので抜かしてビット全探索。
#need_to_buildと同じフラグが立ったものだけ、Ｂｕｉｌｄして値段を検索
min_money = 100000000000000000

for i in range(2**(N-1)):
  #print("roop start")
  bit_box = [0] * (N-1)
  for j in range(N-1):
    if (i>>j)&1:
      bit_box[N-1-1-j] = 1
  #print(bit_box)
  if bit_box.count(1) != need_to_build:
    #print("not match")
    #print(bit_box)
    pass
    
  
  else:
    #試すものがここに残る。
    #print("try parameters")
    #print(bit_box)
    building_list = copy.deepcopy(A_list)
    use_money = 0
    highest_building = building_list[0]
    for k in range(0,N-1):
      if bit_box[k] == 1:
        #print("build start building No.",k+2)
        
        if highest_building >= building_list[k+1]:
          #print("make higher")
          use_money += (highest_building-building_list[k+1]+1)
          #print("use_money",use_money)
          #print(f"change {building_list[k+1]} to {highest_building+1} ")
          building_list[k+1] = highest_building+1
          highest_building = building_list[k+1]
          #print("building now",building_list)
        else:
          pass
          #print("stay")
               
    min_money = min(min_money,use_money)
    #print("result",min_money)
    del building_list
    
print(min_money)

Submission status: Wrong Answer

Solution code:
import itertools
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]!=max(a[:i+1]):
                sm+=max(a[:i+1])-a[i]+1
                a[i]=max(a[:i+1])+1
    if c.count(1)==K:
        ans=min(ans,sm)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

def main(n,k,a):
    arr = []
    locmax = 0
    for i in a:
        arr.append(locmax)
        locmax = max(locmax,i)

    ans = 2**60
    for c in combinations(range(1,n),k-1):
        cost = 0
        prev = a[0]
        for i in c:
            if a[i]<=prev:
                cost += max(prev,arr[i])+1-a[i]
            prev = max(prev,arr[i])+1
        ans = min(ans,cost)
    if k==1:
        ans = 0
    print(ans)

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

def main(n,k,a):
    arr = []
    locmax = 0
    for i in a:
        arr.append(locmax)
        locmax = max(locmax,i)

    ans = 2**60
    for c in combinations(range(1,n),k-1):
        cost = 0
        prev = a[0]
        for i in c:
            if a[i]<=prev:
                cost += max(prev,arr[i])+1-a[i]
            prev = max(prev,arr[i])+1
        ans = min(ans,cost)
    if k==1:
        ans = 1
    print(ans)

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

def main(n,k,a):
    arr = []
    locmax = 0
    for i in a:
        arr.append(locmax)
        locmax = max(locmax,i)

    ans = 2**60
    for c in combinations(range(1,n),k-1):
        cost = 0
        prev = a[0]
        for i in c:
            if a[i]<=prev:
                cost += max(prev,arr[i])+1-a[i]
            prev = max(prev,arr[i])+1
        ans = min(ans,cost)
    print(ans)

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

def main(n,k,a):
    arr = []
    locmax = 0
    for i in a:
        arr.append(locmax)
        locmax = max(locmax,i)

    ans = 2**60
    for c in combinations(range(1,n),k-1):
        cost = 0
        prev = a[0]
        for i in c:
            cost += max(prev,arr[i])+1-a[i]
            prev = max(prev,arr[i])+1
        ans = min(ans,cost)
    print(ans)

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Wrong Answer

Solution code:
from itertools import product
n, k = list(map(int, input().split()))
al = list(map(int, input().split()))
INF = float("inf")
ans = INF
for bit in product([0, 1], repeat=(n-1)):
    if sum(bit)+1 >= k:
        t = 0
        pre = al[0]
        for i, a in enumerate(al):
            if i != 0:
                if bit[i-1] == 1:
                    t += max(0, (pre+1)-al[i])
                    pre = max(al[i], pre+1)
                    continue
                pre = max(pre, al[0])
        ans = min(ans, t)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n, k = list(map(int, input().split()))
al = list(map(int, input().split()))
INF = float("inf")
ans = INF
for bit in product([0, 1], repeat=(n-1)):
    if sum(bit)+1 >= k:
        aal = al[:]
        t = 0
        pre = al[0]
        for i, a in enumerate(aal):
            if i != 0:
                if bit[i-1] == 1:
                    t += max(0, (pre+1)-al[i])
                    pre = max(al[i], pre+1)
        ans = min(ans, t)
print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
for bit in range(1<<(n-1)):
  cost = 0
  cand = [0]*(n-1)
  for i in range(n-1):
    if bit & 1<<i: cand[i] = 1
  if cand.count(1) != k-1: continue
  prev = a[0]
  for i in range(1, n):
    if cand[i-1]:
      cost += prev-a[i]+1
      prev += 1
  ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    ans = 10 ** 12

    for i in range(2 ** n):
        highest = a_list[0]
        cost = 0
        cnt = 0

        for j in range(n):
            if (i >> j) & 1:
                cnt += 1
                if j == 0:
                    continue
                if highest < a_list[j]:
                    highest = a_list[j]
                else:
                    highest += 1
                    cost += highest - a_list[j]

        if cnt < k:
            continue

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    ans = 10 ** 12

    for i in range(2 ** n):
        lst = []

        for j in range(n):
            if (i >> j) & 1:
                lst.append(j)

        if len(lst) < k:
            continue

        highest = a_list[0]
        cost = 0

        for j in range(1, n):
            if highest <= a_list[j]:
                highest = a_list[j]
            else:
                if j in lst:
                    highest += 1
                    cost += highest - a_list[j]

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, input().split())
a = [int(i) for i in input().split()]  #;print(a)
bar = [0] * n
for i in range(1, n):
    bar[i] = max(a[i-1], bar[i-1])
#print(bar)  

ans = float('inf')
for idx in combinations(range(1, n), k-1):
    x0 = a[0] ;dif = 0
    #print(idx)
    for i in range(k-1):
        if x0 < bar[idx[i]]:
            break   #    x0 = bar[i]
        else:
            if a[idx[i]] > x0:
                x0 = a[idx[i]]
            else:
                dif += x0 - a[idx[i]] + 1
                x0 = x0 + 1
    ans = min(ans, dif)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, input().split())
a = [int(i) for i in input().split()]  #;print(a)
bar = [0] * n
for i in range(1, n):
    bar[i] = max(a[i-1], bar[i-1])
#print(bar)  

ans = float('inf')
for tup in combinations(a[1:], k-1):
    x0 = a[0] ;dif = 0
    for i in range(k-1):
        if x0 <= bar[i]:
            break
        else:
            if tup[i] > x0:
                x0 = tup[i]
            else:
                dif += x0 - tup[i] + 1
                x0 = x0 + 1
    ans = min(ans, dif)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, input().split())
a = [int(i) for i in input().split()]  #;print(a)

ans = float('inf')
for tup in combinations(a[1:], k-1):
    x0 = a[0] ;dif = 0
    for i in range(k-1):
        if tup[i] > x0:
            x0 = tup[i]
        else:
            dif += x0 - tup[i] + 1
            x0 = x0 + 1
    ans = min(ans, dif)
if k ==1:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, k = map(int, input().split())
a = [int(i) for i in input().split()]  #;print(a)

ans = float('inf')
for tup in combinations(a[1:], k-1):
    x0 = a[0] ;dif = 0
    for i in range(k-1):
        if tup[i] > x0:
            x0 = tup[i]
        else:
            dif += x0 - tup[i] + 1
            x0 = x0 + 1
    ans = min(ans, dif)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
# 小課題１
# cost = 0
# for i in range(1,n):
#    if a[i] < a[i-1] + 1 :
#        cost += a[i-1] + 1 - a[i]
#        a[i] = a[i-1] + 1
# print(cost)

ans = 10**100
for i in range(1,2**n,2):
    if k != sum([ i>>j & 1 for j in range(n)]) :
        continue
    kijun = a[0]
    cost = 0
    for j in range(1,n):
        if ((i>>j) & 1) :
            if a[j] <= kijun :
                cost += (kijun + 1 - a[j])
                kijun = a[j] + cost
            else :
                kijun = a[j]
        else :
            kijun = max(kijun,a[j])
    ans = min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
# 小課題１
# cost = 0
# for i in range(1,n):
#    if a[i] < a[i-1] + 1 :
#        cost += a[i-1] + 1 - a[i]
#        a[i] = a[i-1] + 1
# print(cost)

ans = 10**100
for i in range(1,2**n,2):
    if k != sum([ i>>j & 1 for j in range(n)]) :
        continue
    kijun = a[0]
    cost = 0
    for j in range(1,n):
        if ((i>>j) & 1) :
            if a[j] <= kijun :
                cost += (kijun + 1 - a[j])
                kijun = a[j] + cost
            else :
                kijun = a[j]
    ans = min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
cost = 0
for i in range(1,n):
    if a[i] < a[i-1] + 1 :
        cost += a[i-1] + 1 - a[i]
        a[i] = a[i-1] + 1
print(cost)

Submission status: Wrong Answer

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

ans = 10**12
for i in range(1, 2**n, 2):
    if not i & 1 or k != sum([i >> j & 1 for j in range(n)]):
        continue
    pre = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            tmp = max(pre - a[j] + 1, 0)
            pre = a[j] + tmp
            cost += tmp
    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 = 10**9
for i in range(1, 2**n, 2):
    if not i & 1 or k != sum([i >> j & 1 for j in range(n)]):
        continue
    pre = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            tmp = max(pre - a[j] + 1, 0)
            pre = a[j] + tmp
            cost += tmp
    ans = min(ans, cost)
print(f'{ans}\n')

Submission status: Wrong Answer

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

ans = 10**9
for i in range(1, 2**n, 2):
    if not i & 1 or k != sum([i >> j & 1 for j in range(n)]):
        continue
    pre = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            tmp = max(pre - a[j] + 1, 0)
            pre = a[j] + tmp
            cost += tmp
    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 = 10**9
for i in range(1 << n - 1, 2**n):
    if not i & 1 or k != sum([i >> j & 1 for j in range(n)]):
        continue
    pre = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            tmp = max(pre - a[j] + 1, 0)
            pre = a[j] + tmp
            cost += tmp
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)

    def test_入力例3(self):
        input = """2 2
7 8"""
        output = """0"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        cost = 0
        target = a0+1
        for i, a in enumerate(A):
            if a > target:
                target = a+1
            if (1 << i) & bit == (1 << i):
                cost += max(0, target-a)
                target = a + max(0, target-a) + 1
        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        cost = 0
        target = a0+1
        for i, a in enumerate(A):
            if (1 << i) & bit == (1 << i):
                cost += max(0, target-a)
                target = a + max(0, target-a) + 1
        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        tmp = 0
        t = a0+1
        for i, a in enumerate(A):
            if (1 << i) & bit == (1 << i):
                tmp += max(0, t-a)
                t = a + max(0, t-a)+1
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        tmp = 0
        n = 1
        for i, a in enumerate(A):
            if (1 << i) & bit == (1 << i):
                tmp += max(0, a0-a+n)
                n += 1
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        tmp = 0
        n = 1
        for i, a in enumerate(A):
            if (1 << i) & bit == (1 << i):
                tmp += max(0, a0-a)+n
                n += 1
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

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

ans = 10**20
for A in itertools.combinations(a[1:], k-1):
    a_max = a[0]
    tmp = 0
    for AA in A:
        if AA <= a_max:
            tmp += a_max-AA+1
            a_max += 1
        else:
            a_max = AA
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**18
for A in itertools.combinations(a[1:], k-1):
    a_max = a[0]
    tmp = 0
    for AA in A:
        if AA <= a_max:
            tmp += a_max-AA+1
            a_max += 1
        else:
            a_max = AA
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**18
for A in itertools.combinations(a[1:], k-1):
    a_max = a[0]
    tmp = 0
    for AA in A:
        if AA <= a_max:
            tmp += a_max-AA+1
            a_max += 1

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**9
for A in itertools.combinations(a[1:], k-1):
    a_max = a[0]
    tmp = 0
    for AA in A:
        if AA <= a_max:
            tmp += a_max-AA+1
            a_max += 1

    ans = min(ans, tmp)
print(ans)