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 
input = sys.stdin.readline

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

min_cost = 10**11
for i in range(2**n):
    height = 0
    k_count = 0
    cost = 0
    for j in range(n):
        if (i>>j) & 1:
            if an[j] <= height:
                cost += height - an[j] + 1
                height += 1
            else:
                height = an[j]
            k_count += 1
        height = max(height, an[j])
    if k_count >= k:
        min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:

def main():
    N, K = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    cost = float('inf')
    for i in range(2**N):
        b = a.copy()
        costtmp = 0
        for j in range(N):
            if (i>>j) & 1:
                maxb = max(b[:j+1])
                if maxb >= a[j+1]:
                    costtmp += maxb + 1 - a[j+1]
                    b[j+1] = maxb + 1
        check = 0
        for k in range(1, N+1):
            maxbk = max(b[:k])
            if maxbk < b[k]:
                check += 1
        if check >= K:
            cost = min(cost, costtmp)
        
    print(cost)


if __name__ == "__main__":
    main()

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:
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])
        else:
            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:
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
    temp,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
        else:
            if a[k+1]>=kijun+1:
                kijun = a[k+1]
                continue
            temp += (kijun+1)-a[k+1]
            kijun += 1
    ans = min(ans,temp)
print(ans)

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:
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!=bit.count(1):
        continue
    temp,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
        else:
            if a[k+1]>=kijun+1:
                kijun = a[k+1]
                continue
            temp += (kijun+1)-a[k+1]
            kijun += 1
    ans = min(ans,temp)
print(ans)

Submission status: Accepted

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

def f(p):
    ret = 0
    ma = 0
    for i, a in enumerate(A):
        if p[i] == 1:
            if ma == 0:
                pass
            else:
                if ma >= a:
                    ret += ma - a + 1
                    ma += 1
        ma = max(ma, a)
    return ret

ans = 10 ** 20
for comb in combinations(range(N), K):
    p = [1 if i in comb else 0 for i in range(N)]
    #if sum(p) < K: continue
    #print(p)
    ans = min(ans, f(p))

print(ans)

Submission status: Accepted

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

def f(p):
    ret = 0
    ma = 0
    for i, a in enumerate(A):
        if p[i] == 1:
            if ma == 0:
                pass
            else:
                if ma >= a:
                    ret += ma - a + 1
                    ma += 1
        ma = max(ma, a)
    return ret

ans = 10 ** 20
for p in product(range(2), repeat=N):
    if sum(p) < K: continue
    #print(p)
    ans = min(ans, f(p))

print(ans)

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')
n, k = map(int, cin[0].split(' '))
a = list(map(int, cin[1].split(' ')))

ret = float('inf')
for idx in range(2**(n)):
    colors = 0
    res = 0
    left = 0
    for i in range(n):
        if (idx>>i) & 1:
            colors += 1
            res += max(left+1 - a[i] , 0)
            left = max(a[i], left+1)
        else:
            colors += 1 if left < a[i] else 0
            left = max(left, a[i])


    if colors >= k:
        ret = min(ret, res)

print(ret)

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')
n, k = map(int, cin[0].split(' '))
a = list(map(int, cin[1].split(' ')))

ret = float('inf')
for idx in range(2**(n)):
    colors = 0
    res = 0
    left = 0
    for i in range(n):
        if (idx>>i) & 1:
            colors += 1
            res += max(left+1 - a[i] , 0)
            left += 1
        # else:
        #     colors += 1 if left < a[i] else 0

        left = max(a[i], left)

    if colors >= k:
        ret = min(ret, res)

print(ret)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 10 ** 20
for i in range(2 ** n):
    total = 0
    data = a.copy()
    highest = a[0] - 1
    cnt = 0
    for j in range(n):
        if i >> j & 1:
            cnt += 1

    if cnt == k:
        for j in range(n):
            if i >> j & 1:
                if highest >= data[j]:
                    total += highest - data[j] + 1
                    data[j] = max(highest + 1, data[j])
            highest = max(highest, data[j])
        ans = min(ans, total)
        #print(data)
    
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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


def getCost(selects, a):
    cost = 0
    pre = a[0]#見える高さ
    for i in range(1,len(a)):
        if i in selects:
            costi = max(0, pre-a[i]+1)
            cost += costi
            if costi > 0:
                pre = pre+1
        pre = max(pre,a[i])
    return cost


def main():
    n,k = na()
    a = na()
    ans = float('inf')
    for i in range(pow(2,n)):
        selects = []
        for j in range(n):
            if ((i>>j) & 1):
                selects += [j]
        if len(selects) != k:
            continue
        ans = min(ans, getCost(selects,a))
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
k-=1
n-=1
c=(1<<k)-1
b=10**18
while c<1<<n:
    w=a[0]
    t=0
    f=1
    for i in range(n):
        if c>>i&1:
            t+=max(0,w-a[i+1]+1)
            w=max(a[i+1],w+1)
        else:
            if a[i+1]>w:
            	f=0
            	break
    if f:
        b=min(b,t)
    x=c&-c
    y=c+x 
    c=((c&~y)//x>>1)|y 
print(b)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
if k==1:
    print(0)
    exit()
a=list(map(int,input().split()))
k-=1
n-=1
c=(1<<k)-1
b=10**18
while c<1<<n:
    w=a[0]
    t=0
    f=1
    for i in range(n):
        if c>>i&1:
            t+=max(0,w-a[i+1]+1)
            w=max(a[i+1],w+1)
        else:
            if a[i+1]>w:
            	f=0
            	break
    if f:
        b=min(b,t)
    x=c&-c
    y=c+x 
    c=((c&~y)//x>>1)|y 
print(b)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

def solve():
    import copy

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

    if K == 1:
        print(0)
        return

    # 最も左にある建物を除く、N-1個の建物について、絶対に見えるようにするかしないかをbit全探索する
    ans = float("inf")
    for bit in range(2**(N-1)):  # 2**14 = 16384
        tmpAs = copy.deepcopy(As)
        highest = tmpAs[0]
        total = 0
        see = 1  # 見えるビルの数
        for i in range(N-1):  # 14
            if bit>>i&1:
                see += 1
                if tmpAs[i+1] <= highest:
                    total += (highest-tmpAs[i+1])+1
                    tmpAs[i+1] = highest+1
            highest = max(highest, tmpAs[i+1])

        if see >= K:
            ans = min(ans, total)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**19
for i in range(2**n):
    colors = 0
    height = 0
    res = 0
    for j in range(n):
        if (i>>j)%2:
            colors += 1
            need = max(0,height - a[j] +1)
            res += need
            height += 1
            
        height = max(a[j] ,height)
    if colors >= k:ans = min(ans,res)
    
print(ans)

Submission status: Accepted

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

ans = 1 << 60
for i in range(1 << N):
    if i % 2 == 0:
        continue
    
    selected = [j for j in range(N) if i & (1 << j)]
    if len(selected) != K:
        continue
    
    h_max = a[0]
    cost = 0
    for j in range(1, N):
        if j in selected:
            if a[j] <= h_max:
                cost += h_max + 1 - a[j]
                h_max += 1
            else:
                h_max = a[j]
        else:
            h_max = max(h_max, a[j])
    
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 10**12
for cmb in combinations(range(1,n),k-1):    
  cost = 0
  h = A[0]
  
  for i in range(1,n):    
    if i in cmb: 
      if A[i] > h:        
        h = A[i]      
      else:
        cost += h - A[i] + 1
        h += 1    
    h = max(h,A[i])
        
  ans = min(ans,cost)
          
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
li = list(map(int, input().split()))
min_ = 10**12
for i in range(1<<n):
    max_height = li[0]
    money = 0
    can_look = 0
    li_h = []
    for j in range(n):
        if j != 0:
            max_height = max(max_height, li_h[j-1])
        #j番目が見えるようにする
        if j == 0:
            can_look += 1
            li_h.append(li[0])
            continue
        if (i>>j)&1:
            can_look += 1
            if li[j] <= max_height:
                li_h.append(max_height+1)
            else:
                li_h.append(li[j])
        else:
            li_h.append(li[j])
    if can_look >= k:
        money = sum(li_h) - sum(li)
        min_ = min(min_, money)

print(min_)

Submission status: Accepted

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

res = 1 << 60 # 最小値が知りたいので答えの初期値はでかい数で
for i in range(1<<n): # k 個のビルが条件を満たすとし、その選び方をbit全探索する。選んだビル数がk以外の時はcontinueという方法で
    if(i%2 == 0): continue # 先頭のビルを見ないのは不可能なので一つ目のbitは必ず立っている必要がありその必要十分条件は「奇数であること」（最初のbitが1）

    use_idx = [0 for _ in range(n)] # どのビルに着目するか 0: 無視
    use_cnt = 0 # 着目するビルの数 kになる時だけ考える
    for j in range(n):
        if(i & (1<<j)):
            use_idx[j] = 1 # 1: 着目
            use_cnt += 1 # ＋＋着目

    if(use_cnt != k): continue # k個のビルに着目することだけを考える

    sm = 0 # 一つ目、先頭。いじる必要はないのでコストも0
    mx = a[0] # 先頭の高さが暫定最大の高さ
    for j in range(1, n):

        if(use_idx[j]): # 二つ目からみていく
            if(a[j] <= mx): # もし暫定最大の高さがこのビル以上の高さならば
                sm += mx+1 - a[j] # このビルは最大＋１の高さまで最低伸ばす必要があり
                mx += 1 # その高さが暫定最大の高さになる

        mx = max(mx, a[j]) # 着目するビルかどうかにかかわらず暫定最大高さは更新される（これをif(use)内に書くとだめだよ。見ないからと言って透明にはならないので）

    res = min(res, sm) # 全てのコストを計算したら暫定最安コストと戦う

print(res)

Submission status: Accepted

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

ans = 10 ** 12
for i in range(1, 2 ** N):
    if bin(i)[2:].count('1') != K: continue
    tmp = 0
    hmax = a[0]
    for j in range(1, N):
        if (i >> j) & 1:
            h = max(hmax + 1, a[j])
            tmp += h - a[j]
            hmax = h
        else:
            hmax = max(hmax, a[j])
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as cmb
n, k = map(int, input().split())
A = list(map(int, input().split()))
highest = [A[0]] * n
for i in range(1, n):
  highest[i] = max(A[i], highest[i-1])

def cost_calc(pattern):
  cost = 0
  max_height_re = 0
  for num in pattern:
    cost += max(max_height_re, highest[num]) - A[num]
    max_height_re = max(max_height_re, highest[num]) + 1
  return cost

max_val = float("inf")
for pattern in cmb(range(n), k):
  max_val = min(max_val, cost_calc(pattern))
print(max_val)

Submission status: Accepted

Solution code:
from itertools import combinations as cmb
import copy
n, k = map(int, input().split())
A = list(map(int, input().split()))
highest = [A[0]] * n
for i in range(1, n):
  highest[i] = max(A[i], highest[i-1])

def cost_calc(pattern):
  cost = 0
  max_height_re = 0
  A_copy = copy.copy(A)
  for num in pattern:
    cost += max(max_height_re, highest[num]) - A[num]
    max_height_re = max(max_height_re, highest[num]) + 1
  return cost

max_val = float("inf")
for pattern in cmb(range(n), k):
  max_val = min(max_val, cost_calc(pattern))
print(max_val)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for i in range(2**(N-1)):
        if bin(i).count("1") != K-1:
            continue
        height = A[0]
        tmp = 0
        for j in range(N-1):
            if (i >> j) & 1:
                height += 1
                if A[j+1] >= height:
                    height = A[j+1]
                    continue
                tmp += height - A[j+1]
            height = max(height, A[j+1])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for pattern in combinations(range(1,N), K-1):
        height = A[0]
        tmp = 0
        for i in range(1,N):
            if i in pattern:
                height += 1
                if A[i] >= height:
                    height = A[i]
                    continue
                tmp += height - A[i]
            height = max(height, A[i])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for pattern in combinations(range(1,N), K-1):
        height = A[0]
        tmp = 0
        p_s = set(pattern)
        for i in range(1,N):
            if i in p_s:
                height += 1
                if A[i] >= height:
                    height = A[i]
                    continue
                tmp += height - A[i]
            height = max(height, A[i])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, input().split()) 
    a = [int(i) for i in input().split()]
    c = [int(i) for i in range(1, n)]
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, input().split()) 
    a = np.array(input().split(), np.int32)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, readline().split()) 
    a = np.array(readline().split(), np.int32)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, readline().split()) 
    a = np.array(readline().split(), np.int64)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in comb:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 10**15
for i in range(2**N):
    if bin(i).count('1')<K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

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

ans = 10**15
for i in range(2**N):
    if bin(i).count('1')!=K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

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

ans = 10**12
for i in range(2**N):
    if bin(i).count('1')!=K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
N,K = map(int,input().split())
a = [int(i) for i in input().split()]
ans = float("INF")

for c in comb(range(1,N),K-1):
    cnt = 0
    color = 0
    mh = a[0]
    for i in range(1,N):
        if i == c[color]:
            cnt += max(mh-a[i]+1,0)
            color += 1
            if color == K-1: break
            mh = max(mh+1,a[i])
        else:
            mh = max(mh,a[i])
    ans = min(cnt ,ans)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
a = [int(i) for i in input().split()]
ans = float("INF")
for i in range(1<<N):
    cnt = 0
    tmp = a[:]
    m = tmp[0]
    for j in range(1,N):
        if i >> j & 1 and m >= tmp[j]:
            cnt += m - tmp[j] + 1
            tmp[j] = m + 1
        m = max(m,tmp[j])
    color = 1
    m = tmp[0]
    for j in range(1,N):
        if tmp[j] > m:
            color += 1
            m = tmp[j]
    if color >= K: ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k == 1:
  print(0)
  exit()
  
b = [int(i)+1 for i in range(n-1)]
ans = float('inf')
import itertools
for j in itertools.combinations(b, k-1):
  s = list(j)
  now_high = a[0]
  cost = 0
  for l in range(1,n):
    if l in s:
      if a[l] > now_high:
        now_high = a[l]
        continue
      else:
        cost += (now_high-a[l]+1)
        now_high += 1
    now_high = max(now_high, a[l])
  ans =  min(ans,cost)
print(ans)

Submission status: Accepted

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


ans = 10 ** 11
for  i in range(2 ** N):
    if bin(i).count("1") != K:
        continue
    max_height = 0
    height_num = 0
    for j in range(N):
        if i >> j & 1:
            if a[j] <= max_height:
                height_num += (max_height + 1 - a[j])
                max_height += 1
            else:
                max_height = a[j]
        else:
            max_height = max(max_height, a[j])
    ans = min(ans, height_num)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    
    select = []
    for i in range(1 << n):
        comb = [None] * n
        cnt = 0
        for j in range(n):
            if (i >> j) & 1:
                comb[j] = 1
                cnt += 1
            else:
                comb[j] = 0
        if cnt == k:
            select.append(comb)

    ans = float('inf')
    for s in select:
        tmp_a = list(a)
        tmp_ans = 0
        for i in range(1, n):
            max_height = max(tmp_a[:i])
            if s[i] and max_height >= tmp_a[i]:
                tmp_ans += max_height - tmp_a[i] +1
                tmp_a[i] = max_height + 1
        ans = min(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float('inf')
def search(x):
    if len(x)==n:
        if x.count(1)>=k:
            global ans
            m = a[0]
            c = 0
            for i in range(1,n):
                if x[i]==1:
                    c += max(0,m-a[i]+1)
                    m = max(m+1,a[i])
                m = max(m,a[i])
            ans = min(ans,c)
    else:
        search(x+[1])
        search(x+[0])
search([])
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(1,2**n):
    num=format(i,"b").zfill(n)
    point=0
    if num.count("1")!=k:continue
    highest=A[0]
    for j in range(1,n):
        if highest>=A[j] and  num[j]=="1":
            point +=highest-A[j]+1
            highest +=1
        highest=max(highest,A[j])
    ans=min(ans,point)

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(1,2**n):
    num=format(i,"b").zfill(n)
    point=0
    if num.count("1")!=k:continue
    highest=A[0]
    for j in range(1,n):
        if num[j]=="1":
            point +=max(0,highest-A[j]+1)
            highest=max(highest+1,A[j])
        highest=max(highest,A[j])
    ans=min(ans,point)

print(ans)

Submission status: Accepted

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

res = 1<<60
for i in range(1<<n):    
    if i % 2 == 0: continue

    use_idx = [0 for _ in range(n)]
    use_cnt = 0
    for j in range(n):
        if i & (1<<j):
            use_idx[j] = 1
            use_cnt += 1
    
    if use_cnt != k: continue

    sm = 0
    mx = a[0]
    for j in range(1, n):
        if use_idx[j]:
            if a[j] <= mx:
                sm += mx+1 - a[j]
                mx += 1
        mx = max(mx, a[j])
    
    res = min(res, sm)

print(res)

Submission status: Accepted

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

res = 10 ** 15

for bit in range(2 ** N):
    cnt = 0
    for i in range(N):
        if (bit >> i) & 1:
            cnt += 1

    if cnt < K:
        continue

    cost = 0
    height = A[0]
    if (bit >> 0) & 1:
        for i in range(1, N):
            if (bit >> i) & 1 and height >= A[i]:
                cost += height - A[i] + 1
                height += 1
            elif height < A[i]:
                height = A[i]

        res = min(res, cost)

print(res)

Submission status: Accepted

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

res = 10 ** 15

for bit in range(2 ** N):
    cnt = 0
    for i in range(N):
        if (bit >> i) & 1:
            cnt += 1

    if cnt < K:
        continue

    cost = 0
    height = 0
    for i in range(0, N):
        if (bit >> i) & 1 and height >= A[i]:
            cost += height - A[i] + 1
            height += 1
        elif height < A[i]:
            height = A[i]

    res = min(res, cost)

print(res)

Submission status: Accepted

Solution code:
import itertools

N,K = map(int,input().split())
a = list(map(int,input().split()))
lis = [x for x in range(1,N)]
m = 10**15

for con in itertools.combinations(lis, K-1):
  mm = 0
  f = a[0]
  for i in range(K-1):
    if f+1 <= a[con[i]]:
      f = a[con[i]]
    else:
      mm += (f+1) - a[con[i]]
      f += 1
    for j in range(con[i]-1):
      if a[j] >= f:
        mm = 10**15
        break
    else:
      continue
    break
  m = min(m,mm)
  
print(m)

Submission status: Accepted

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

ans = 10**18
for bit in product(range(2), repeat=n):#k+1個以上の建物の高さを増やす必要はない
    ma = 0
    cost = 0
    see = 0
    for i in range(n):
        ai = a[i]
        if ai>ma:
            see += 1
            ma = ai
        elif bit[i]:
            ma = ma + 1
            see += 1
            co = ma - ai
            cost += co
    if see>=k:
        ans = min(ans, cost)
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
INF = int(1e18)
def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    p = [i for i in range(1,n)]
    #必ず見えるようにする建物の組合せを決める
    #左端の建物は常に見えるので注意する
    ans = INF
    for i in combinations(p, k-1):
        s = set(i)
        cost = 0
        mx = a[0]
        for j in range(1, n):
            if j in s:
                if a[j] > mx:
                    mx = a[j]
                    continue
                mx += 1
                cost += mx-a[j]
            mx = max(mx, a[j])
        ans = min(cost, ans)                
    print(ans)
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
money = float('inf')
for bit in range(1 << N):
    S = [0]*N
    for i in range(N):
        if bit & (1 << i):
            S[i] = 1
    if S.count(1) >= K:
        sumnum = 0
        maxh = A[0]
        for i in range(1, N):
            if S[i] == 1:
                if A[i] > maxh:
                    maxh = A[i]
                else:
                    maxh += 1
                    sumnum += (maxh - A[i])
            else:
                maxh = max(maxh, A[i])

        money = min(money, sumnum)
print(money)