Problem:


				Max Score: 350 Points 

Problem Statement

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

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

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

					You cannot decrease height of buildings. 

					Calculate the minimum cost of satisfying Chokudai's objective. 

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

Input Format

N K
a_1 a_2 a_3 ... a_N

Output Format

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

Constraints

1 ≤ K ≤ N ≤ 15

1 ≤ a_i ≤ 10^9

Scoring

						Subtask 1 [120 points] 

N = K

						Subtask 2 [90 points] 

N ≤ 5

a_i ≤ 7

						Subtask 3 [140 points] 

There are no additional constraints.

Sample Input 1

5 5
3949 3774 3598 3469 3424

Sample Output 1

1541

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

Sample Input 2

5 3
7 4 2 6 4

Sample Output 2

7

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



Sample input:
5 5
3949 3774 3598 3469 3424


Sample output:
1541

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**10
for B in combinations(range(1,N),K-1):
    mx = A[0]
    score = 0
    for n in range(1,N):
        if n in B:
            if A[n] <= mx:
                mx += 1
                score += (mx - A[n])
            else:
                mx = A[n]
        else:
            mx = max(mx, A[n])
    mn = min(mn, score)
print (mn)

Submission status: Wrong Answer

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

ans=10**100
for i in range(2**(N-1)):
  bit=format(i,'0'+str(N)+'b')
  bit=list(map(int,bit))
  maxh=A[0]
  price=0
  color=1
  for n in range(N):
    if n==0:continue
    elif bit[n]==0:
      if A[n]>maxh:
        color+=1
        maxh=A[n]
    else:
      maxh+=1
      price+=maxh-A[n]
      color+=1
  if color>=K and price<=ans:
    ans=price
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = 10**11 # min(res, ) を取る場合はresを大きい数に取る

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) # 最初に見えている色の種類
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) # test_a には左から写る予定のK個のビルの高さが入っている
    for i in range(len(test_a)-1):
        if test_a[i] > test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
    res = min(res, cost)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = (max(a)+K) * K # min(res, ) を取る場合はresを大きい数に取る

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) # 最初に見えている色の種類
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) # test_a には左から写る予定のK個のビルの高さが入っている
    for i in range(len(test_a)-1):
        if test_a[i] > test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
    res = min(res, cost)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = max(a) * K # min(res, ) を取る場合はresを大きい数に取る

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) # 最初に見えている色の種類
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) # test_a には左から写る予定のK個のビルの高さが入っている
    for i in range(len(test_a)-1):
        if test_a[i] > test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
res = min(res, cost)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = a[len(a)-1] * K # min(res, ) を取る場合はresを大きい数に取る

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) # 最初に見えている色の種類
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) # test_a には左から写る予定のK個のビルの高さが入っている
    for i in range(len(test_a)-1):
        if test_a[i] > test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
res = min(res, cost)

print(res)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n > k:
    for i in range(n-k):
        m = min(a)
        a.remove(m)

ans = 0
for i in range(k-1):
    if int(a[i] - a[i+1]) >= 0:
        ans += int(a[i] - a[i+1] + 1)
        a[i+1] += int(a[i] - a[i+1] + 1)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n > k:
    for i in range(n-k):
        m = min(a)
        a.remove(m)

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

print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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] > A[0]]) >= K - 1:
    ans[i] = cost
    #print(AA,bin(i),cost)
    
print(min(ans))

Submission status: Wrong Answer

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
  con = 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
      con += 1
    if con == K - 1:
      break
  #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: Wrong Answer

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
  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: Wrong Answer

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])
    a = AA[j + 1]
    if ((i >> j) & 1) and a <= m:
      cost += (m - a + 1)
      AA[j + 1] = m + 1
      con += 1
  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: Wrong Answer

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])
    #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: Wrong Answer

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(x2,ans)

print(mi)

Submission status: Wrong Answer

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: Wrong Answer

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
    if bit[0]==1:
        x2=[0]*n
        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 ans!=0 and check(x2,n,k):
        mi=min(mi,ans)

print(mi)

Submission status: Wrong Answer

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

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
    if sum(bit)>=k and 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
    if ans!=0:
        mi=min(mi,ans)
print(mi)

Submission status: Wrong Answer

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

mi = float('inf')
for bit in b:
    ans = 0
    s1=0
    if sum(bit)>=k and bit[0]==1:
        for i in range(n):
            if bit[i]==1:
                s2=x[i]
                if s2<s1:
                    ans+=s1-s2+1
                    s1+=1
                else:
                    s1=s2
    if ans!=0:
        mi=min(mi,ans)
print(mi)

Submission status: Wrong Answer

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
    # 1個目以降からK-1個抜き出して階段状にする
    for i in itertools.combinations(range(1, N), K-1):
        cost_sum = 0
        prev_height = a[0]
        for j in i:
            if a[j]<=prev_height:
                cost_sum += (prev_height+1)-a[j]
                prev_height += 1
            else:
                prev_height = a[j]
        ans = min(cost_sum, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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
    # 1個目以降からK-1個抜き出して階段状にする
    for i in itertools.combinations(range(1, N), K-1):
        cost_sum = 0
        for j, e in enumerate(i):
            cost_sum += (a[0]+j+1)-a[e]
        ans = min(cost_sum, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
l=[False for i in range(n)]
now=[i for i in a]
ans_true=float('inf')

for i in range(2**n):
  for j in range(n):
    if i>>j & 1:
      l[j]=True
  
  ans=0
  for s in range(n):
    if l[s]==False:
      continue

    if l[s]==True and s!=0:
      if now[s]<max(now[:s]):
        ans+=max(now[:s])-now[s]+1
        now[s]=max(now[:s])+1

  if k<=sum(l):
    ans_true=min(ans,ans_true)
  now=[x for x in a]
  l=[False for x in range(n)]

print(ans_true)

Submission status: Wrong Answer

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(n):
        if b[i-1]<b[i]:
            ok+=1
        else:
            b[i]=b[i-1]
    if ok>=3:
        ans=min(ans,c)
print(ans)

Submission status: Wrong Answer

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
    if k >= K and p < cost:
        cost = p

print(cost)

Submission status: Wrong Answer

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

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
    if k >= K and p < cost:
        cost = p

print(cost)

Submission status: Wrong Answer

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 (i>>j)&1:
            color += 1
            highest = highest + 1
            money += highest - a[j]
        else:
            if a[j] > highest:
                color += 1
                highest = a[j]
    if color >= k:
        ans = min(ans,money)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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))
print("\n")

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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: Wrong Answer

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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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: Wrong Answer

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: Wrong Answer

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
        heigt = max(height, a[j + 1])
 
    if can_see >= K-1:
        ans = min(ans, cost)
 
print(ans)

Submission status: Wrong Answer

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
        heigt = max(height, a[j + 1])

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

print(ans)

Submission status: Wrong Answer

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
        heigt = max(height, a[j + 1])
    
    if can_see >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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番目以降で見えるようにするビルを選択
    if sum(bit) < K -1:
        continue

    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
        elif b == 1:
            height = a[j + 1]
        heigt = max(height, a[j + 1])

    ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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: Wrong Answer

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 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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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: Wrong Answer

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 + N - i < target:
        return float('inf')
    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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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: Wrong Answer

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 + N - i < target:
        return float('inf')
    if i >= len(a):
        return float('inf')
    if can_see >= target:
        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)
    if can_see == target:
        # print('height', height)
        # print('can_see', can_see)
        # print('cost', cost)
        return cost
    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))