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:
from itertools import product   # bit全探索: list(itertools.product([0,1], repeat=n))
from copy import deepcopy   # 配列のコピー: B = deepcopy(A)

inf = 1000000000    # 1,000,000,000

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

    num_list_copy = deepcopy(num_list)

    ans = inf

    for bit in list(product([0, 1], repeat = n)):
        count = bit.count(1)
        if count < k:
            continue
        if bit[0] != 1:
            continue
        tmp = 0
        for i in range(1,n):
            if bit[i] != 1:
                continue
            x = 1
            while(bit[i-x] != 1):
                x += 1
            if i - x < 0:
                x = i
            if num_list[i-x] >= num_list[i]:
                add_hight = num_list[i-x] - num_list[i] + 1
                num_list[i] += add_hight
                tmp += add_hight
        num_list = deepcopy(num_list_copy)
        if ans > tmp:
            ans = tmp
            # print(bit)
        # ans = min(ans, tmp)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product   # bit全探索: list(itertools.product([0,1], repeat=n))
from copy import deepcopy   # 配列のコピー: B = deepcopy(A)

inf = 1000000000    # 1,000,000,000

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

    num_list_copy = deepcopy(num_list)

    ans = inf

    for bit in list(product([0, 1], repeat = n)):
        count = bit.count(1)
        if count < k:
            continue
        if bit[0] != 1:
            continue
        # print(bit)
        tmp = 0
        for i in range(1,n):
            if bit[i] != 1:
                continue
            x = 1
            while(bit[i-x] != 1):
                x += 1
            if num_list[i-x] >= num_list[i]:
                add_hight = num_list[i-x] - num_list[i] + 1
                num_list[i] += add_hight
                tmp += add_hight
        num_list = deepcopy(num_list_copy)
        ans = min(ans, tmp)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(1<<n):
    if (bin(i)[2:].rjust(n,"0")).count("1")<k:
        continue
    p,q=0,0
    if i&1!=1:
        continue
    for j in range(n):
        if i>>j&1:
            if p>=a[j]:
                q+=p-a[j]+1
                p+=1
            else:
                p=a[j]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

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

for i in range(1<<n):
    if (bin(i)[2:].rjust(n,"0")).count("1")<k:
        continue
    p,q=0,0
    if i&1!=1:
        continue
    for j in range(n):
        if i>>j&1:
            if p>=a[j]:
                q+=p-a[j]+1
                p+=1
            else:
                p=a[j]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

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

import itertools
for l in itertools.combinations(list(range(n)),k):
    p,q=0,0
    if l[0]!=0:
        continue
    for i in l:
        if p>=a[i]:
            q+=p-a[i]+1
            p+=1
        else:
            p=a[i]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ans=10**18
ll=[]
tmp=0
for i in a:
    if tmp>i:
        ll.append(tmp)
    else:
        ll.append(i)
        tmp=i
import itertools
for l in itertools.combinations(list(range(n)),k):
    p,q=ll[l[0]],0
    if p!=a[l[0]]:
        continue
    else:
        p-=1
    for i in l:
        if p>=a[i]:
            q+=p-a[i]+1
            p+=1
        else:
            p=a[i]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ans=10**18
ll=[]
tmp=0
for i in a:
    if tmp>i:
        ll.append(tmp)
    else:
        ll.append(i)
        tmp=i
import itertools
for l in itertools.combinations(list(range(n)),k):
    p,q=ll[l[0]],0
    for i in l:
        if ll[i]>a[i]:
            q+=max(ll[i],p)-a[i]+1
            p=max(ll[i],p)+1
        elif ll[i]==a[i]:
            q+=max(ll[i],p)-a[i]+1
            p+=1    
        else:
            p=a[i]
    if ans>q:
        ans=q

print(ans-k)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ans=10**18
ll=[]
tmp=0
for i in a:
    if tmp>i:
        ll.append(tmp)
    else:
        ll.append(i)
        tmp=i
import itertools
for l in itertools.combinations(list(range(n)),k):
    p,q=0,0
    for i in l:
        if ll[i]>a[i]:
            q+=max(ll[i],p)-a[i]+1
            p=max(ll[i],p)+1
        elif ll[i]==a[i]:
            q+=p-a[i]+1
            p+=1    
        else:
            p=a[i]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ans=10**18
ll=[]
tmp=0
for i in a:
    if tmp>i:
        ll.append(tmp)
    else:
        ll.append(i)
        tmp=i
import itertools
for l in itertools.combinations(list(range(n)),k):
    p,q=0,0
    for i in l:
        if ll[i]>a[i]:
            q+=max(ll[i],p)-a[i]+1
            p=max(ll[i],p)+1
        else:
            p=a[i]
    if ans>q:
        ans=q

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

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

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

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

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

    for i in range(len(visible_building_indices)-1):
        if a[visible_building_indices[i]] >= a[visible_building_indices[i+1]]:
            tmp += a[visible_building_indices[i]] - a[visible_building_indices[i+1]] + 1
            a[visible_building_indices[i+1]] = a[visible_building_indices[i]] + 1

    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

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

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

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

    for i in range(visible_building_indices[0]):
        if a[i] >= a[visible_building_indices[0]]:
            tmp += a[i] - a[visible_building_indices[0]] + 1

    for i in range(len(visible_building_indices)-1):
        if a[visible_building_indices[i]] >= a[visible_building_indices[i+1]]:
            tmp += a[visible_building_indices[i]] - a[visible_building_indices[i+1]] + 1
            a[visible_building_indices[i+1]] = a[visible_building_indices[i]] + 1

    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

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

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

if __name__ == '__main__':
    square869120Contest4_B()

"""

"""

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

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

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

if __name__ == '__main__':
    square869120Contest4_B()

"""

"""

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    # See:
    # https://atcoder.jp/contests/s8pc-4/submissions/2122030
    if n == 1:
        print(0)
        exit()

    for bit in range(1 << (n - 1)):
        color_count = 1
        cost = 0
        height_min = a[0]

        for j in range(n - 1):
            if height_min < a[j + 1]:
                color_count += 1
                height_min = a[j + 1]

            if bit & (1 << j):
                cost += height_min - a[j + 1] + 1
                color_count += 1
                height_min += 1

        if color_count >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    for bit in range(1 << n):
        numbers = list()

        for j in range(n):
            if (bit >> j) & 1:
                if j == 0:
                    continue

                numbers.append(j)

        cost = 0
        height_min = a[0]
        height = [a[0]]

        for number in numbers:
            if a[number] <= height_min:
                cost += height_min - a[number] + 1
                height_min += 1
            else:
                height_min = a[number]

            height.append(height_min)

        if len(height) >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

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

    for bit in range(1 << n):
        numbers = list()

        for j in range(n):
            if (bit >> j) & 1:
                numbers.append(j)

        cost = 0
        height_min = a[0]
        height = [a[0]]

        for number in numbers:
            if number == 0:
                continue

            if a[number] <= height_min:
                cost += height_min - a[number] + 1
                height_min += 1
            else:
                height_min = a[number]

            height.append(height_min)

        if len(height) >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    for bit in range(1 << n):
        numbers = list()

        for j in range(n):
            if (bit >> j) & 1:
                numbers.append(j)

        cost = 0
        height_min = a[0]
        height = [a[0]]

        for number in numbers:
            if number == 0:
                continue

            if a[number] <= height_min:
                cost += height_min - a[number] + 1
                height_min += 1
            else:
                height_min = a[number]

            height.append(height_min)

        if len(height) >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    for bit in range(1 << n):
        numbers = list()

        for j in range(n):
            if (bit >> j) & 1:
                numbers.append(j)

        cost = 0
        height_min = a[0]
        height = [a[0]]

        for number in numbers:
            if number == 0:
                continue

            if a[number] < height_min:
                cost += height_min - a[number] + 1
                height_min += 1
            else:
                height_min = a[number]

            height.append(height_min)

        if len(height) >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[n]-A[n], 0)
            if n!=0 and acc[n-1]==acc[n]:
                cost+=1
        else:
            cost=max(prev-A[n]+1, acc[n]-A[n]+1, 0)
        sm+=cost
        prev=A[n]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[comb[i]]-A[comb[i]], 0)
            if comb[i]!=0 and acc[comb[i]-1]==acc[comb[i]]:
                cost+=1
        else:
            cost=max(prev-A[comb[i]]+1, 0)
        sm+=cost
        prev=A[comb[i]]+cost
    ans=min(ans, sm)
print(ans)