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: Runtime Error

Solution code:

#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        # bit立っている建物の番号のリストを求める
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        # K色の色を見えるようにしたときのcostを求める
        if len(buildings) == K:
            print(f"\nbits: {bin(bits)}")
            print(f"buildings: {buildings}")
            max_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"max_height: {max_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    # 建物iの高さを増やす必要があるとき
                    if max_height >= l_height_copy[i]:
                        # print("max_height >= l_height[i]")
                        # print(f"diff: {(max_height + 1) - l_height_copy[i]}")
                        cost += (max_height + 1) - l_height_copy[i]
                        # print(f"cost: {cost}")
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
                        # print(f"updated max_height: {max_height}")
                    else:
                        max_height = l_height_copy[i]
                else:
                    if l_height_copy[i] > max_height:
                        # print(f"updated max_height: {max_height}")
                        max_height = l_height_copy[i]
            costs.append(cost)

# print(costs)
print(min(costs))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        # bit立っている建物の番号のリストを求める
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        # K色の色を見えるようにしたときのcostを求める
        if len(buildings) == K:
            print(f"\nbits: {bin(bits)}")
            print(f"buildings: {buildings}")
            max_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"max_height: {max_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    # 建物iの高さを増やす必要があるとき
                    if max_height >= l_height_copy[i]:
                        # print("max_height >= l_height[i]")
                        # print(f"diff: {(max_height + 1) - l_height_copy[i]}")
                        cost += (max_height + 1) - l_height_copy[i]
                        # print(f"cost: {cost}")
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
                        # print(f"updated max_height: {max_height}")
                    else:
                        max_height = l_height_copy[i]
                else:
                    if l_height_copy[i] > max_height:
                        # print(f"updated max_height: {max_height}")
                        max_height = l_height_copy[i]

            costs.append(cost)

print(costs)
print(min(costs))

# ----- 方針 -----
# N > Kとする。
# i個目の建物高さを変更するとき1が立つN個のbitsを考える。
# bitが立っている建物の番号のリストを以下で求める。
# buildings = []
# for i in range(N):
#     if bits & (1 << i):
#         buildings.append(i)
# bitsのうち、K個bitが立っているものを考える。
# bitが立っている番号の建物が必ず見えるように高さを増やしたときのcostを求める。

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
def dfs(index):
    global ans
    if index == N:
        if blst.count(1) == K:
            tmp = a[bisect_left(blst, 1)]
            anstmp = 0
            for i in range(N):
                if blst[i] == 0:continue
                if tmp >= a[i]:
                    anstmp += tmp - a[i] + 1
                    tmp += 1
                else:
                    tmp = a[i]
            ans = min(ans, anstmp)
        return
    for i in range(2):
        blst[index] = i
        dfs(index + 1)
    return

N, K = map(int, input().split())
a = list(map(int, input().split()))
blst = [0] * N
ans = float('inf')
dfs(0)

print(ans - K)

Submission status: Runtime Error

Solution code:
# import math
# import bisect
#import numpy as np
import itertools
import copy
import sys

input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    cmb = list(itertools.combinations([i for i in range(1, n)], k-1))
    ans = INF

    if k > 1:
            for ele in cmb:
                prc = 0
                prev = a[0]
                acp = a.copy()
                for idx in ele:
                    if acp[idx] - prev <= 0:
                        prc += prev - acp[idx] + 1
                        acp[idx] = prev + 1
                    prev = acp[idx]
                cnt = 1
                mh = acp[0]
                for i in range(1, n):
                    if mh < acp[i]:
                        cnt += 1
                        mh = acp[i]
                if cnt >= k:
                    ans = min(ans, prc)
    else:
        ans = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# import math
# import bisect
import numpy as np
import itertools
# import copy
import sys

input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    cmb = list(itertools.combinations([i for i in range(1, n)], k-1))
    ans = INF

    for ele in cmb:
        prc = 0
        prev = a[0]
        for idx in ele:
            cur = a[idx]
            if cur - prev <= 0:
                prc += prev - cur + 1
                cur = prev + 1
            prev = cur
        ans = min(ans, prc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# B - Buildings are Colorful!

import sys
input = sys.stdin.buffer.readline

import itertools

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

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

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

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

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

    ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

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