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

ans = float('inf')
for b in range(1<<(N-1)):
    mxa = A[0]
    k = 1
    cost = 0
    for i,a in enumerate(A[1:]):
        if b&(1<<i):
            c = max(0, mxa+1 - a)
            cost += c
            mxa = max(a, mxa+1)
            k += 1
        else:
            if mxa < a:
                mxa = a
                k += 1
    if k >= K:
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 10000000000000
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: Accepted

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]
                continue

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

Solution code:
from itertools import product as p
n,k=map(int,input().split())
a=list(map(int,input().split()))
an=float("INF")
for i in p([0,1],repeat=n):
    s=0
    c=a[::]
    p=0
    q=0
    for j in range(n):
        if i[j]:
            if s<c[j]:
                p+=1
                s=c[j]
            else:
                q+=s+1-c[j]
                c[j]=s+1
                p+=1
                s+=1
        else:
            if s<c[j]:
                p+=1
                s=c[j]
    if p>=k:
        an=min(q,an)
print(an)

Submission status: Accepted

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

# 見る建物を決め打ち、コストを計算して最小値が答え。
# 左端は見えてしまうので、それを除いたn-1個からk-1個を選ぶ

from itertools import combinations

ptn = combinations(range(1, n), k - 1)

ans = 10 ** 19
for p in ptn:
  totalcost = 0
  repA = A[:]
  for itr, val in enumerate(p):
    cost = max(0, max(repA[:val]) + 1 - repA[val])
    repA[val] += cost
    totalcost += cost
  ans = min(ans, totalcost)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

# 使った建物の番号集合ごとに、右端の高さと総コストを持つ：一意

N,K = map(int,input().split())
A = [int(x) for x in input().split()]

L = 1<<N
right = np.zeros(L,dtype=np.int64)
total = np.zeros(L,dtype=np.int64)

for i,a in enumerate(A):
    bit = 1<<i
    right[bit:2*bit] = np.maximum(right[:bit]+1,a)
    np.maximum(right[:bit],a,out=right[:bit])
    total[bit:2*bit] = (right[bit:2*bit] - a) + total[:bit]

popcount = np.zeros(L,dtype=np.int32)
rng = np.arange(L)
for _ in range(15):
    popcount += rng&1
    rng >>= 1

answer = total[popcount >= K].min()
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
aa = inpl()
NotLooking = list(itertools.combinations(range(1,N),N-K))

ans = INF
for NL in NotLooking:
    h = aa[0]
    tmp = 0
    for i in range(1,N):
        if i in NL:
            h = max(h,aa[i])
            continue
        else:
            if h < aa[i]:
                h = aa[i]
            else:
                tmp += h+1 - aa[i]
                h = h+1
    ans = min(tmp,ans)

print(ans)

Submission status: Accepted

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()

# 累積MAX
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:
            # 1つめは累積MAXとの差分
            cost=max(acc[n]-A[n], 0)
            # 一番左じゃなくて、1つ手前の累積MAXより高くないなら+1
            if n!=0 and acc[n-1]==acc[n]:
                cost+=1
        else:
            # 2つめ以降は、max(1つ前に選んだやつ, 1つ手前の累積MAX)との差分+1でmax取る
            cost=max(max(prev, acc[n-1])-A[n]+1, 0)
        sm+=cost
        prev=A[n]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Accepted

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-1]-A[n]+1, 0)
        sm+=cost
        prev=A[n]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a2,ans = [0],float("inf")
for i in range(n): a2.append(max(a[i],a[-1]))
def g(q):
	c,f = 0,1
	if sum(q)<k-1: f = 0
	else:
		m = a[0]
		for i in range(n-1):
			if q[i]: m,c = max(a[i+1],m+1),c+max(m+1-a[i+1],0)
			elif m<a[i+1]:
				f = 0
				break
	if f: return c
	else: return float("inf")
for i in product((0,1),repeat=n-1): ans = min(ans,g(i))
print(ans)

Submission status: Accepted

Solution code:
def b_buildings_are_colorful(N, K, A):
    import itertools
    # 注目するビルの番号(左端を除くK-1個)の組
    attention_building = itertools.combinations(range(1, N), K - 1)
    ans = float('inf')
    for comb in attention_building:
        raised_a = A[:]  # 左から注目しているビルが見えるように高さを調節したあとのビルの高さ
        max_height = A[0]  # 高さを調整するとき、そのビルより左にあるビルより高くしなければならない
        for k in range(1, N):
            if k in comb:
                # 左からk番のビルは注目しているものだった。
                # 左から見えるように、高さを調整する
                if raised_a[k] <= max_height:
                    raised_a[k] = max_height + 1
            max_height = max(max_height, raised_a[k])

        cost = 0
        for k in range(N):
            cost += raised_a[k] - A[k]
        ans = min(ans, cost)
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(b_buildings_are_colorful(N, K, A))

Submission status: Accepted

Solution code:
def b_buildings_are_colorful(N, K, A):
    import itertools
    combination = itertools.combinations(range(1, N), K - 1)
    ans = float('inf')
    for comb in combination:
        tmp = A[:]
        max_height = A[0]
        for k in range(1, N):
            if k in comb:
                if tmp[k] <= max_height:
                    tmp[k] = max_height + 1
            max_height = max(max_height, tmp[k])

        delta = 0
        for k in range(N):
            delta += tmp[k] - A[k]
        ans = min(ans, delta)
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(b_buildings_are_colorful(N, K, A))

Submission status: Accepted

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

ans = 10**18
for P in product(range(2), repeat=N-1):
    if sum(P) < K-1:
        continue
    res = 0
    base = A[0]
    for i in range(N-1):
        if P[i]:
            if A[i+1] <= base:
                res += (base+1 - A[i+1])
                base += 1
            else:
                base = A[i+1]
        else:
            if base < A[i+1]:
                res += (A[i+1] - base)
                base = A[i+1]
    ans = min(ans, res)
print(ans)

Submission status: Accepted

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

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

ans = float('inf')
for bs in range(1<<(N-1)):
    colors = 1
    cost = 0
    tmp = src[0]
    for k in range(N-1):
        if tmp < src[k+1]:
            colors += 1
            tmp = src[k+1]
            continue
        if bs&(1<<k):
            cost += tmp - src[k+1] + 1
            colors += 1
            tmp += 1
    if colors >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=float("inf")
for i in xrange(1<<n):
    cnt=0
    li=[]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt<k-1:continue
    tmp=0
    h=a[0]
    for j in li:
        for l in xrange(j):
            h=max(h,a[l])
        tmp+=max(h+1-a[j],0)
        h=max(h+1,a[j])
    ans=min(ans,tmp)
print ans

Submission status: Accepted

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

ans = 10**12
for b in range(1<<n):
    c = 0
    for i in range(n):
        if ((b>>i)&1) == 1:
            c += 1
    if c != k: continue
    t = 0
    h = 0
    for i in range(n):
        if ((b>>i)&1) == 0:
            h = max(h, a[i])
            continue
        if h < a[i]:
            h = a[i]
            continue
        if h >= a[i]:
            t += h - a[i] + 1
            h += 1
            continue
    ans = min(ans, t)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
bills = list(map(int,input().split()))
ans = 0
k = 0
while k < K:
	k = 0
	cost =[]
	cosd = {}
	tatekae = {}
	maxh = 0
	for bi,b in enumerate(bills):
		if b > maxh:
			cost.append(0)
			maxh = b
			k = k + 1
		else:
			c = maxh - b + 1
			cost.append(c)
			maxh2 = maxh + 1
			tatekae[bi] = []
			for b2i,b2 in enumerate(bills[bi:]):
				if maxh2 < b2:
					break
				elif maxh2 == b2:
					c = c + 1
					maxh2 = maxh2 + 1
					tatekae[bi].append(b2i + bi)
			cosd[bi] = c
	if k >= K:
		break
	a = min(cosd.items(),key =lambda x: x[1])[0]
	ans = ans + cosd[a]
	bills[a] = bills[a] + cost[a]
	for t in tatekae[a]:
		bills[t] = bills[t] + 1
	k = k + 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    req = 0
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**38
for mask in xrange(ma):
    b = [a[0]]
    ma = a[0]
    pr = a[0]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
        elif a[i] > pr:
            b.append(a[i])
            
        pr = max(pr,a[i])
    if len(b)>=k:
        res = min(res, solve(b[:k]))
print res

Submission status: Accepted

Solution code:
from itertools import combinations
n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 10 ** 12
for p in combinations(range(n), k):
    p = list(p)[::-1]
    ma = 0
    res = 0
    for j in xrange(n):
        if p and j == p[-1]:
            if ma < a[j]:
                ma = a[j]
            else:
                res += ma + 1 - a[j]
                ma += 1
            p.pop()
        else:
            if ma < a[j]:
                ma = a[j]
    if ans > res:
        ans = res
print ans

Submission status: Runtime Error

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

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

#1つ目のタワーは足すことがないので抜かしてビット全探索。
#need_to_buildと同じフラグが立ったものだけ、Ｂｕｉｌｄして値段を検索
min_money = 100000000000000000
samebuilding_flag = False
for i in range(2**(N-1)):
  #print("roop start")
  bit_box = [0] * (N-1)
  for j in range(N-1):
    if (i>>j)&1:
      bit_box[N-1-1-j] = 1
      if N-1-j in can_see:
        #print("flag apeeard")
        samebuilding_flag = True
        
  #print(bit_box)
  if bit_box.count(1) != need_to_build:
    #print("not match")
    #print(bit_box)
    pass
    
  elif samebuilding_flag == True:
    samebuilding_flag = False
    pass
  
  else:
    #試すものがここに残る。
    #print("try parameters")
    #print(bit_box)
    building_list = copy.deepcopy(A_list)
    use_money = 0
    
    bit_box_start = bit_box.index(1)
   #print("BBS",bit_box_start)
    for _ in range(0,len(can_see))[::-1]:
      if can_see[_] < bit_box_start+1:
        highest_building = building_list[can_see[_]]
        break
    
    
    
    for k in range(0,N-1):
      if bit_box[k] == 1:
        #print("build start building No.",k+2)
        
        if highest_building >= building_list[k+1]:
          #print("make higher")
          use_money += (highest_building-building_list[k+1]+1)
          #print("use_money",use_money)
          #print(f"change {building_list[k+1]} to {highest_building+1} ")
          building_list[k+1] = highest_building+1
          highest_building = building_list[k+1]
          #print("building now",building_list)
        else:
          #print("stay")
          #print("building now",building_list)
          pass
          
    #print("use_money",use_money)
    min_money = min(min_money,use_money)
    #print("result",min_money)
    del building_list
    
print(min_money)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

# a[1:]で大きさが上位K-1についてフラグを付ける
# フラグがついているのと前回のものの差分＋１をしていく
# この処理をK-1回行った段階で終了させる

target_list = sorted(buildings[1:], reverse=True)[:K-1]

i = 0 #ターゲットリストの添え字
cost = 0
before_building = buildings[0]

for building in buildings[1:]:

    if building == target_list[i]:
        cost += max(before_building - building + 1, 0)
        before_building += 1
        # print('cost: ', cost)
        # print('before_building: ', before_building)
        i += 1

    if i == K:
        break

print(cost)

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(n-len(ini_seen)),k-len(ini_seen)):
    sm=0
    work=0
    xtoken=0
    count=1
    for i in range(1,n):
        if i in ini_seen:
            count+=1
            if work<ini[i] : work=ini[i]
            else:
                work+=1
                sm+=work-ini[i]
        elif i==x[xtoken]+count:
            work+=1
            sm+=work-ini[i]
            xtoken+=1
            if xtoken==k-len(ini_seen):break



    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Submission status: Runtime Error

Solution code:
#<14>
#(point)
#全探索によってどの建物が見えるようにするかを決めて必要な費用を計算。
#建物が見える =　それより左にある建物maxより１大きいなので左から線形に
#最大値を更新、計算量は高々n_c_kのcombについてO(N)の操作なのでおｋ
from itertools import combinations
n, k = map(int,input().split())
a = list(map(int,input().split()))
mn = 10 ** 18

for b in combinations(range(1, n),k - 1):#一番左は固定
    mx = a[0] #初期値=一番左の建物
    score = 0
    for j in range(1, n):
        if j in b:#見えなあかん建物なら
            if a[j] <= mx : #低けりゃ高くする
                mx += 1
                score += (mx - a[j])
            else: #高さが十分なら最大値を更新するだけ
                mx = a[n]
        else:
            mx = max(mx, a[j])#別に見えんくてもいい建物なら最大値更新
    mn = min(mn, score)
print(mn)

Submission status: Runtime Error

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

ans = 10**20
count = 0
tempbin = ""
maxx = 0

for i in range(2**n):
    tempbin = format(i,'b')
    tempbin = tempbin.zfill(n)
    count = 0
    templist = alist.copy()
    if tempbin.count("1") != k:
        continue
    for j in range(1,n):
        if tempbin[j] == "1":
            maxx = max(templist[:j])
            if maxx >= templist[j]:
                count += maxx + 1 - templist[j]
                templist = maxx + 1
    ans = min(ans,count)

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=sum(sorted(a[1:])[::-1])[:k-1]
s=sum(i for i in range(2,k+1))
print(max(s-b,0))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=sum(sorted(a[1:]])[::-1])[:k-1]
s=sum(i for i in range(2,k+1))
print(max(s-b,0))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
// #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);i++)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}
const ll inf = 1LL<<60;

int main() {
  int n,k,high;cin>>n>>k;
  ll ans=inf;
  ll now=0;
  int color=0;

  vector<int> a(n);
  rep(i,n){
    cin>>a[i];
  }
  for(int i=0;i<(1<<n);i++){
    high=a[0];
    color=1;
    now=0;
    for(int j=1;j<n;j++){
      if(1 & (i>>j)){
        if(a[j]<=high){
          now+=high-a[j]+1;
          high=high+1;
          color+=1;
        }else{
          color+=1;
        }
      }else{
        if(high<a[j]){
          high=a[j];
          color+=1;
        }
      }
    }
    if(k<=color){
      ans=min(ans,now);
    }
  }
  cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 10
# if N==K:
#     cost=0
#     for i in range(1,N):
#         if height2[i-1]>=height2[i]:
#             cost+=height2[i-1]-height2[i]+1
#             height2[i]+=height2[i-1]-height2[i]+1
#     print(cost)
for i in range(2 ** N):
    count=1
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")>=K:
        for j in range(N):
            if i >> j & 1:
                if j!=0:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]+=tarou-height2[j]+1

        if ans > cost
            ans = cost

print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

from itertools import combinations

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

minc=10**12
ai=[i for i in range(N)]
for i in combinations(ai,K):
    ac=a[:]
    cost=0
    i=list(i)
    for j in range(1,K):
        costt=max(max(ac[:i[j]])-ac[i[j]]+1,0)
        ac[i[j]]+=costt
        costa+=costt
    minc=min(cost,minc)
print(minc)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

from itertools import combinations

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

upend=N-1
for i in range(N):
    if a[i]>a[i+1]:
        upend=i
        break
minc=10**12
for i in combinations(a[upend+1:],K):
    cost=0
    l=[a[j] for j in range(upend+1)]+list(i)
    for j in range(1,K):
        costt=max(l[j-1]-l[j]+1,0)
        l[j]+=costt
        cost+=costt
    minc=min(cost,minc)

print(minc)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

from itertools import combinations

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

minc=10**12
for i in combinations(a,K):
    cost=0
    for j in range(1,K):
        costt=max(i[j-1]-i[j]+1,0)
        i[j]+=costt
        cost+=costt
    minc=min(cost,minc)

print(minc)

Submission status: Runtime Error

Solution code:
import copy

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

ans = [None 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
  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
  print(AA,bin(i),cost)
  if len([AA[i] for i in range(1,N) if AA[i] > A[0]]) >= K - 1:
    ans[i] = cost
  
print(min(ans))

Submission status: Runtime Error

Solution code:
import copy

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

ans = 10 ** 12
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
  con = 0
  for j in range(N - 1):
    m = max(AA[:j + 1])
    W
    #print(AA[:j + 1])
    a = AA[j + 1]
    if ((i >> j) & 1) and A[j + 1] <= m:
      cost += (m - a + 1)
      AA[j + 1] = m + 1
      con += 1
    if con == K - 1:
      break
  if len([AA[i] for i in range(1,N) if AA[i] > A[0]]) == K - 1:
    ans = min(cost,ans)
  
print(ans)

Submission status: Runtime Error

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
                use[u]= left_max+1
        ans.append(cst)   
print(min(ans))

Submission status: Runtime Error

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()))

if K == 0:
  break
 
 
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: Runtime Error

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()))

if K == 0:
  break
 
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: Runtime Error

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,kijun=0,a[0]
        for j in range(n):
            if not bit[j]:
                kijun=max(kijun,a[j+1])
                continue
            if a[j+1]>=kijun+1:
                kijun=a[j+1]
                continue
            cost+=kijun+1-a[j+1]
            kijun+=1
        ans=min(ans,cost)
print(ans)

Submission status: Runtime Error

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,kijun=0,a[0]
        for j in range(n):
            if not bit[j]:
                kijun=max(kijun,a[k+1])
            elif a[k+1]>=kijun+1:
                kijun=a[k+1]
            else:
                cost+=kijun+1-a[k+1]
                kijun+=1
        ans=min(ans,cost)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=float("inf")
for i in range(2**n):
    if sum(bin(i))==k and (i>>0)&1:
        l=[]
        tmp=0
        for j in range(n):
            if (i>>j)&1: l.append(a[j])
        for k in range(len(l)-1):
            p=+l[k]+1-l[k+1]
            if p>0:
                tmp+=p
                l[k+1]+=p
        ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

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

ret = 0
target = [a[0]+i for i in range(1, k)]
for idx in range(2**(n-1)):
    cnt = 0
    tmp = 0
    for i in range(n):
        if (idx>>i) & 1:
            tmp += target[cnt] - a[i+1] if target[cnt] > a[i+1] else 0
            cnt += 1

        if cnt == len(target):
            if ret == 0:
                ret = tmp
            else:
                ret = min(ret, tmp)
            break

print(f'{ret}\n')

Submission status: Runtime Error

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)
            idx += 1
            mh = max(mh+1,a[i])
        if color == K-1: break
    ans = min(cnt ,ans)
print(ans)

Submission status: Runtime Error

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

res = 1000000000
for bit in range(2 ** N):
    b = [int(bin(bit)[i + 2]) for i in range(len(bin(bit)) - 2)]
    if b.count(1) >= K:
    	b.reverse()
        b_index = -1
        height = 0
        cnt = 0
        while True:
            sub = 0
            if 1 in b[b_index + 1:]:
                b_index = b[b_index + 1:].index(1) + b_index + 1
            else:
                break

            if A[b_index] - height <= 0:
                sub += height - A[b_index] + 1
                cnt += sub
                height = A[b_index] + sub
            else:
                height = A[b_index]

        res = min(res, cnt)

print(res)

Submission status: Runtime Error

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

ans = 1145141919810364364334
for i in range(1,2**n):
    ls = [0] * n
    qq = []
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            qq.append(j)
            
    if sum(ls) < k:
        continue
        
    elif ls[0] == 1:
        t = []
        for j in qq:
            t.append(a[j])
        
        mt = t[0]
        cost = 0
        for j in range(len(qq) - 1) :
            if t[j+1] <= mt:
                cost += (mt + 1 - t[j+1])
                mt += 1
            else:
                mt = max(t[j+1] ,a[:qq[j+1]])
    else:
        continue
                
    ans = min(ans,cost)
    
print(ans)