Problem:


				Max Score: 350 Points 

Problem Statement

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

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

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

					You cannot decrease height of buildings. 

					Calculate the minimum cost of satisfying Chokudai's objective. 

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

Input Format

N K
a_1 a_2 a_3 ... a_N

Output Format

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

Constraints

1 ≤ K ≤ N ≤ 15

1 ≤ a_i ≤ 10^9

Scoring

						Subtask 1 [120 points] 

N = K

						Subtask 2 [90 points] 

N ≤ 5

a_i ≤ 7

						Subtask 3 [140 points] 

There are no additional constraints.

Sample Input 1

5 5
3949 3774 3598 3469 3424

Sample Output 1

1541

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

Sample Input 2

5 3
7 4 2 6 4

Sample Output 2

7

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



Sample input:
5 5
3949 3774 3598 3469 3424


Sample output:
1541

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for bit in range(1 << N):
        if (not (bit & 1)) or bin(bit).count('1') != K:
            continue

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if bit & (1 << i):
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float("inf")
for i in range(1,2**n):
    l = [j for j in range(n) if i>>j&1]
    if l[0] != 0 or len(l) != k:
        continue
    m = 0
    s = 0
    for j in range(n):
        if (j in l) and (a[j] <= m):
            s += m+1-a[j]
            m += 1
        m = max(m,a[j])
    #print(l,s)
    ans = min(ans,s)

print(ans)

Submission status: Accepted

Solution code:

from itertools import product


def main():
    N, K = list(map(int, input().split()))
    a = list(map(int, input().split()))
    find = 0
    for i in range(1, N):
        if a[i-1] < a[i]:
            find += 1
    if find >= K:
        print(0)
        return

    first = a.pop(0)

    ans = float('inf')

    for bits in product((0, 1), repeat=N-1):
        build = a.copy()
        changeBuild = bits
        find = 1
        score = 0
        if sum(changeBuild) == 0:
            continue
        for i, v in enumerate(changeBuild):
            if i == 0:
                nowmax = first
            else:
                maxbuild = max(build[:i])
                nowmax = max(first, maxbuild)

            if v == 1 and nowmax >= build[i]:
                score += nowmax-build[i]+1
                build[i] = nowmax+1
            if i == 0 and first < build[i]:
                find += 1
            if i >= 1 and nowmax < build[i]:
                find += 1
        if find >= K:
            ans = min(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

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

min_cost = 10 ** 12
for indexes in combinations(range(N), r=K):
    indexes = set(indexes)
    highest = 0
    cost = 0
    for i in range(N):
        height = A[i]
        if i in indexes and height <= highest:
            dh = highest - height + 1
            cost += dh
            height += dh
        highest = max(highest, height)
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
import copy

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

ans = [10 ** 12 for i in range(2 ** (N - 1))]
seen = 1  #[[A[j] for j in range(i,N) if A[j] > A[i]] for i in range(0,N)]

for i in range(2 ** (N - 1)):
  AA = copy.deepcopy(A)
  cost = 0
  s = str(bin(i))[2:]
  if s.count("1") >= K:
    continue
    
  for j in range(N - 1):
    m = max(AA[:j + 1])
    a = AA[j + 1]
    if ((i >> j) & 1) and a <= m:
      cost += (m - a + 1)
      AA[j + 1] = m + 1
  
  if len([AA[i] for i in range(1,N) if AA[i] > max(AA[:i])]) >= K - 1:
    ans[i] = cost
    #print(AA,bin(i),cost)
    
print(min(ans))

Submission status: Accepted

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

money = 10 ** 12

for i in range(2 ** N):
  B = copy.copy(A)
  #print(B)
  count = 0
  money2 = 0
  for j in range(N):
    if ((i >> j) & 1):
      count += 1
      if j != 0:
        x = max(0, max(B[:j]) - B[j] + 1)
        if x != 0:
          B[j] = max(B[:j]) + 1
        money2 += x
        #print(i, j, x, money2, count)
  if count >= K:
    money = min(money, money2)
      
print(money)

Submission status: Accepted

Solution code:
import sys, itertools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    a = LI()
    ans = INF
    for i in range(2**N):
        cost_sum = 0
        cnt = 0
        prev_height = 0
        for j in range(N):
            if (i>>j)&1:
                if a[j]<=prev_height:
                    cost_sum += (prev_height+1)-a[j]
                    prev_height += 1
                else:
                    prev_height = a[j]
                cnt += 1
            prev_height = max(a[j], prev_height)
        if cnt>=K:
            ans = min(cost_sum, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
#input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
Com = []
for i in range(N):
    Com.append(i)


ans = float('inf')
for com in combinations(Com, K):
    anscom = 0
    thread = 0
    for i, a in enumerate(A):
        if i not in com:
            thread = max(thread, a)
        else:
            if thread < a:
                thread = a
            else:
                anscom += thread + 1 - a
                thread += 1
    ans = min(ans, anscom)
print(ans)

Submission status: Accepted

Solution code:
n , k = map(int, input().split())
x = list(map(int,input().split()))
b = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]
h = [0]*n

def check(li,n,k):
    c=1
    hi=li[0]
    for i in range(1,n):
        if li[i]>hi:
            c+=1
            hi=li[i]
    if c>=k:
        return True
    else:
        return False

for i in range(1,n):
    h[i]=max(h[i-1],x[i-1])

mi = float('inf')
for bit in b:
    ans = 0
    s1=0
    x2=x.copy()
    if bit[0]==1:
        for i in range(n):
            if bit[i]==1:
                s2=x[i]
                if s2<=s1:
                    ans+=s1-s2+1
                    s2=s1+1
                if s2<=h[i]:
                    ans += h[i]-s2+1
                    s2=h[i]+1
                s1=s2
                x2[i]=s2
            else:
                x2[i]=x[i]
    if check(x2,n,k):
        mi=min(mi,ans)

print(mi)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float("inf")
 
for i in range(2**n):
    highest = a[0]
    color = 1
    money = 0
    for j in range(1,n):
        if a[j] > highest:
            color += 1
            highest = a[j]
        elif (i>>j)&1:
            color += 1
            highest = highest + 1
            money += highest - a[j]
        
    if color >= k:
        ans = min(ans,money)
print(ans)

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline


# 高さを変更するかどうかの bool 型配列を作る
def make(i, l):
    if i == N:
        return [l]
    else:
        lc = l[:]
        l.append(False)
        lc.append(True)
        return make(i+1, l) + make(i+1, lc)


def main():
    ans = 15*10**10
    for tf in make(1, [False]):
        peak = A[0]
        count = 1
        cost = 0
        for i in range(1, N):
            if count == K:
                break
            if tf[i]:
                count += 1
                if peak >= A[i]:
                    cost += peak - A[i] + 1
                    peak += 1
                else:
                    peak = A[i]
            else:
                if A[i] > peak:
                    peak = A[i]
                    count += 1
        if count == K:
            ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    main()

Submission status: Accepted

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

import itertools
import sys
list_n = itertools.combinations(range(N),K)
ans = 1000000000000000
for i_list in list_n:#i_list は見ることのできるようにする建物のインデックスのリスト
    a_i = a.copy()
    cost = 0
    for index in i_list:
        if not index == 0:
            m_index = max(a_i[:index])
        else:
            m_index = 0
        if m_index >= a_i[index]:
            cost += m_index - a_i[index] + 1
            #print(m_index - a_i[index] + 1)
            a_i[index] = a_i[index] + m_index - a_i[index] + 1   
    ans = min(ans, cost)
    
print(ans)

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,k=n1()
a=n1()

import itertools
ite=itertools.combinations(range(n),k)

ans=10**20
for line in ite:
    c=0
    b=a.copy()
    for i in range(1,k):
        if b[line[i]]<=b[line[i-1]]:
            plus=b[line[i-1]]-b[line[i]]+1
            b[line[i]]+=plus
            c+=plus
    ok=1
    for i in range(1,n):
        if b[i-1]<b[i]:
            ok+=1
        else:
            b[i]=b[i-1]
    if ok>=k:
        ans=min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
 
N,K=map(int,input().split())
lists=list(map(int,input().split()))
#スタート地点がa_i(1<=i<=N)の場合で固定する
import itertools
seq=[i for i in range(1,N)]
D=list(itertools.combinations(seq,K-1))

answer=float("inf")

def cal(D):
    money=0
    now_height=lists[0]
    K=set(D)
    for i in range(1,N):
        if now_height>=lists[i]:
            if i in K:
                money+=(now_height+1-lists[i])
                now_height+=1
            else:
                #i not in K:
                pass
            
        elif now_height<lists[i]:
            if i in K:
                money+=0
                now_height=lists[i]
            else:
                #i not in K:
                money+=(lists[i]+1-now_height)
                now_height+=1
    return money
for que in D:
    answer=min(answer,cal(que))
print(answer)

Submission status: Accepted

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

if N == 1:
    cost = 0
else:
    cost = 10 ** 11

for i in range(2 ** (N - 1)):
    r = str(format(i, 'b')).zfill(N - 1)
    ma = a[0]
    k = 1
    p = 0
    for j in range(N - 1):
        if r[j] == '1':
            k += 1
            if a[1 + j] > ma:
                ma = a[1 + j]
            elif a[1 + j] <= ma:
                p += ma - a[1 + j] + 1
                ma = ma + 1
        elif r[j] == '0':
            if a[1 + j] > ma:
                ma = a[1 + j]
    if k >= K and p < cost:
        cost = p

print(cost)

Submission status: Accepted

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

for i in range(2**n):
    highest = a[0]
    color = 1
    money = 0
    for j in range(1,n):
        if a[j] > highest:
            color += 1
            highest = a[j]
        elif (i>>j)&1:
            color += 1
            highest = highest + 1
            money += highest - a[j]
        
    if color >= k:
        ans = min(ans,money)
print(ans)

Submission status: Accepted

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

ans=[]
for i in range(1<<n):
    
    if bin(i).count("1")==k:
        cst=0
        use=a.copy()
        for u in range(1,n):
            if(i>>u&1):
                left_max=max(use[:u])
                cst+=left_max-use[u]+1 if left_max>=use[u] else 0
                use[u]= max(left_max+1, use[u])
        ans.append(cst)
print(min(ans))

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　

import sys

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


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        return cost

    # 端まで探索したとき
    if i == len(a):
        return float('inf')

    # 建物 i を選ばない場合
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see + 1, i=i + 1)
    # print('cost1', cost1, 'can_see', can_see, 'i', i)

    # 建物　i を選んだ場合
    cost += max(0, height + 1 - a[i])
    can_see += 1
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    # print('cost2', cost2)

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　

import sys

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


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        return cost

    # 端まで探索したとき
    if i == len(a):
        return float('inf')

    # 建物 i を選ばない場合
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see + 1, i=i + 1)
    # print('cost1', cost1, 'can_see', can_see, 'i', i)

    # 建物　i を選んだ場合
    cost += max(0, height + 1 - a[i])
    can_see += 1
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    # print('cost2', cost2)

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 分割統治法 ver
import sys

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

if K == 0:
    sys.exit()

def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost

    # 端まで探索したとき
    if i == len(a):
        return float('inf')

    # 建物 i を選ばない場合
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost1', cost1, 'can_see', can_see, 'i', i)

    # 建物　i を選んだ場合
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost2', cost2)

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 分割統治法 ver
import sys

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

if K == 0:
    sys.exit()

def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see >= target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost

    # 端まで探索したとき
    if i == len(a):
        return float('inf')

    # 建物 i を選ばない場合
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost1', cost1, 'can_see', can_see, 'i', i)

    # 建物　i を選んだ場合
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost2', cost2)

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 全探探索　ver
 
import sys
 
N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
 
ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  # 左から2番目以降で見えるようにするビルを選択
 
    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j+1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
        height = max(height, a[j + 1])
 
    if can_see >= K-1:
        ans = min(ans, cost)
 
print(ans)

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 全探探索　ver

import sys

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

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  # 左から2番目以降で見えるようにするビルを選択

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
        height = max(a[j + 1], height)

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 全探探索　ver

import sys

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

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  # 左から2番目以降で見えるようにするビルを選択

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
            height = a[j + 1]

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　
# 全探探索　ver

import sys

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

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  # 左から2番目以降で見えるようにするビルを選択

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1) & (height < a[j + 1]):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
            height = a[j + 1]

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
# Square869120Contest #4 B - Buildings are Colorful!　

import sys

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


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see >= target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost

    # 端まで探索したとき
    if i == len(a):
        return float('inf')

    # 建物 i を選ばない場合
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost1', cost1, 'can_see', can_see, 'i', i)

    # 建物　i を選んだ場合
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    # print('cost2', cost2)

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Submission status: Accepted

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

min_cost = 10**15
for i in range(2 ** n):
    see_a_ids = []
    for j in range(n):
        if ((i >> j) & 1):
            see_a_ids.append(j)
    
    if len(see_a_ids) < k:
        continue

    curr_max_h = 0
    curr_cost = 0
    for a_i in range(n):
        if a_i in see_a_ids:
            if a_list[a_i] <= curr_max_h:
                h_plus = curr_max_h + 1 - a_list[a_i]
                curr_cost += h_plus
                curr_max_h = curr_max_h+1
            else:
                curr_max_h = a_list[a_i]
        else:
            curr_max_h = max(curr_max_h, a_list[a_i])
    min_cost = min(min_cost, curr_cost)
print(min_cost)

Submission status: Accepted

Solution code:
import itertools

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
max_h = 0
for i, num in enumerate(a):
    b.append(max_h)
    max_h = max(max_h, num)

ans = 9999999999999999999999
for lst in itertools.combinations(range(1, n), k - 1):
    total = 0
    before = a[0]
    for num in lst:
        if a[num] <= b[num] or a[num] <= before:
            total += max(b[num], before) - a[num] + 1
            before = max(b[num], before) + 1
            
    ans = min(ans, total)
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

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

# each bildings'color is different.

ans = 1000000000 * 15 * 15
for x in range(2 ** N):
    bi = bin(x)[2::][::-1]
    bi = bi + ( "0" * (N - len(bi)) )
    higest = A[0]
    bilging = 1
    cost = 0
    for index , a in enumerate(A[1::]) :
        if bi[index+1] == "1" and a <= higest:
            diff = higest - a 
            cost += diff + 1
            higest = a + diff + 1
            bilging += 1
        
        if higest < a :
            bilging += 1
            higest = a
    if bilging >= K:
        ans = min(ans , cost)
print(ans)

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
n,k = LI()
a = LI()

min_val = 20000000000
for i in range(1 << (n-1)):
    count = 0
    val = 0
    pre = a[0]
    for j in range(n-1):
        if(i & (1 << j)):
            count += 1
            if(pre >= a[j+1]):
                val += pre - a[j+1] + 1
                pre = pre + 1
        if(pre < a[j+1]):
            pre = a[j+1]

    if(count >= k-1):
        if(min_val > val):
            min_val = val

print(min_val)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=float("inf")
for i in range(2**n):
    bit=[(i>>j)&1 for j in range(n)]
    if sum(bit)==k and bit[0]:
        cost=0
        kijun=a[0]
        for j in range(1,n):
            if not bit[j]:
                kijun=max(kijun,a[j])
            elif a[j]>=kijun+1:
                kijun=a[j]
            else:
                cost+=kijun+1-a[j]
                kijun+=1
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=float("inf")
for i in range(2**n):
    bit=[(i>>j)&1 for j in range(n)]
    if sum(bit)==k and bit[0]==1:
        cost=0
        kijun=a[0]
        for j in range(1,n):
            if bit[j]==0:
                kijun=max(kijun,a[j])
            elif a[j]>=kijun+1:
                kijun=a[j]
            else:
                cost+=kijun+1-a[j]
                kijun+=1
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

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
    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: Accepted

Solution code:
import itertools

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

amin=10**9*20
for i in itertools.product([0,1], repeat=n):
    if sum(i)==k:
        hs=a[0]
        acnt=0
        h=[]
        for j in range(n):
            if i[j]==1 and j>0:
                if hs>=a[j]:
                    acnt+=hs-a[j]+1
                    hs=hs+1
            if hs<a[j]:
                hs=a[j]
            h.append(hs)
#        print(i,acnt,h)
        amin=min(amin,acnt)
        
print(amin)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 10 ** 20
for bit in product([0, 1], repeat=n):
    if sum(bit) != k or bit[0] == 0:
        continue
    cnt = 0
    tmp = a[0]
    for i, v in enumerate(bit):
        if v == 1:
            if i != 0:
                cnt += max(tmp + 1 - a[i], 0)
                tmp = max(tmp + 1, a[i])
        else:
            tmp = max(tmp, a[i])
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

ans = 10**18
for i in range(1<<N):
    cnt = 0
    cost = 0
    mini = 0
    for j in range(N):
        J = As[j]
        if (i>>j)&1:
            cnt += 1
            if mini>=J:
                cost += mini+1-J
                mini += 1
        mini = max(mini, J)
        if cnt>=K:
            ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import copy
    n, k  = map(int, input().split())
    takasa_lis = list(map(int, input().split()))
   
    ans = 10**200
    
    for i in range(0, 2 ** n, 2):
        test_lis = copy.deepcopy(takasa_lis)
        cnt = 0
        building_cost = 0
        for j in range(1, n):
            if ((i>>j) & 1):
                cnt += 1
                building_cost += max(max(test_lis[0:j]) - test_lis[j] + 1, 0)
                test_lis[j] = max(max(test_lis[0:j])+1, test_lis[j])
            else:
                if test_lis[j] > max(test_lis[0:j]):
                    cnt += 1
        if cnt >= k-1 and ans > building_cost:
            ans = building_cost
    
    print(ans)


    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# B - Buildings are Colorful!
# 全探索、BIT全探索
N, K = map(int, input().split())
A = list(int(x) for x in input().split())

def solve(idx):
    ret = 0
    tmpmax = A[0]
    for i in range(1, idx[-1]+1):
        if A[i] <= tmpmax:
            if i in idx:
                ret += tmpmax - A[i] + 1
                tmpmax += 1
        else:
            tmpmax = A[i]
    return ret

ans = 10**18
for i in range(1<<N):
    idx = []
    for j in range(N):
        if i>>j&1:
            idx.append(j)
    if len(idx)==K and idx[0]==0:
        ans = min(ans, solve(idx))

print(ans)

Submission status: Accepted

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

ans = float('inf')
for i in range(2 ** n):
    res = 0
    cnt = 0
    prev_build = buildings[0]
    for j in range(n):
        if (i >> j) & 1 == 1:
            cnt += 1
            if prev_build >= buildings[j] and not j == 0:
                res += ((prev_build + 1) - buildings[j])
                prev_build = prev_build + 1
            else:
                prev_build = buildings[j]
        else:
            if prev_build < buildings[j]:
                prev_build = buildings[j]

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

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=tuple(map(int,input().split()))
if k==1 or n==1:
    print(0)
    exit()
m=pow(10,12)
l=len(a)-1
for i in range(2**(n-1)):
    cnt=1
    h=a[0]
    num=0
    for j in range(l):
        if (i>>j)&1:
            num+=max(0,h-a[j+1]+1)
            if a[j+1]<=h:
                h+=1
            else:
                h=a[j+1]
            cnt+=1
        else:
            if a[j+1]>h:
                cnt+=1
                h=a[j+1]
    if cnt>=k:
        m=min(m,num)
print(m)

Submission status: Accepted

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

candidate = [[0], [1]]
while True:
    temp = []
    for c in candidate:
        temp.append(c + [0])
        temp.append(c + [1])
    candidate = temp
    if len(temp[0]) == N:
        break

ans = float('inf')
for c in candidate:
    if sum(c) != K:
        continue
    high = a[0]
    temp = 0
    for i, value in enumerate(c):
        if i == 0:
            continue
        if value == 1 and a[i] <= high:
            high += 1
            temp += high - a[i]
        high = max(high, a[i])


    ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
def get_building(i, N):
    ans = [0]*N
    ans[0] = 1
    for ind in range(1, N):
        if i % 2 == 0:
            ans[ind] = 1
        i //= 2
    return ans

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

ans = -1
for i in range(2**(N-1)):
    see_building = get_building(i, N)

    counter = 1
    now_height = a[0]
    cost = 0
    for j in range(1, N):
        if see_building[j] == 1:
            counter += 1
            if a[j] <= now_height:
                cost += (now_height - a[j]) + 1
                now_height += 1
            else:
                now_height = a[j]
        else:
            now_height = max(now_height, a[j])
    
    if counter >= K:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)