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 collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
a = list(map(int, input().split()))
a_sorted = sorted(a[1:])
a_dic = defaultdict(list)
for i in range(len(a)):
  a_dic[a[i]].append(i)
idx = [0]
used = []
cost = 0

for i in range(K-1):
  idx.append(a_dic[a_sorted.pop(-1)].pop(0))
idx.sort()

for j in range(1, len(idx)):
  if a[idx[j-1]] < a[idx[j]]:
    continue
  cost += a[idx[j-1]] + 1 - a[idx[j]]
  a[idx[j]] = a[idx[j-1]] + 1
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
a = list(map(int, input().split()))
a_sorted = sorted(a[1:])
idx = []
height = a[0]

for k in range(K-1):
  idx.append(a.index(a_sorted.pop(-1)))
idx.sort()
for i in idx:
  height += a[i]
cost = a[0]*K + K*(K-1)//2 - height
print(cost)

Submission status: Wrong Answer

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

ans = float('inf')
for bit in range(2**(N-1)):
    pre_num = a_list[0]
    ans_pre = 0
    count = 1
    index = []
    for i in  range(N-1):
        if bit & (1<<i):
            count+=1
            index.append(i+1)
            if pre_num >= a_list[i+1]:
                ans_pre += pre_num-a_list[i+1]+1
            
                pre_num += 1
                
            else:
                pre_num = a_list[i+1]
    if count >= K:
        ans = min(ans, ans_pre)
            
print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
for bit in range(2**(N-1)):
    pre_num = a_list[0]
    ans_pre = 0
    count = 1
    index = []
    for i in  range(N-1):
        if bit & (1<<i):
            count+=1
            index.append(i+1)
            if pre_num >= a_list[i+1]:
                ans_pre += pre_num-a_list[i+1]+1
            
                pre_num += 1
                
            else:
                pre_num = a_list[i+1]
    if count == K:
        ans = min(ans, ans_pre)
            
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
ans=15*10**10
for i in range(2**(n-1)):#1番目は確定だから
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
    if cnt>=k-1:
        ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
ans=15*10**10
for i in range(2**(n-1)):#1番目は確定だから
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
    if cnt==k-1:
        ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]*n
m=0
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
for i in range(n):
    x=a[i]
    if m>x:
        cost[i]=m-x
        a[i]=m
    else:
        m=x
ans=15*10**10
h=a[0]
for i in range(2**(n-1)):#1番目は確定だから
    cnt=0
    s=0
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            s+=cost[j+1]
            s+=max(a[j+1],h+cnt)-a[j+1]
    if cnt==k-1:
        ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]*n
m=0
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
for i in range(n):
    x=a[i]
    if m>x:
        cost[i]=m-x
        a[i]=m
    else:
        m=x
ans=15*10**9
h=a[0]
for i in range(2**(n-1)):#1番目は確定だから
    cnt=0
    s=0
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            s+=cost[j+1]
            s+=max(a[j+1],h+cnt)-a[j+1]
    if cnt==k-1:
        ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]*n
m=0
for i in range(n):
    x=a[i]
    if m>x:
        cost[i]=m-x
        a[i]=m
    else:
        m=x
ans=15*10**9
h=a[0]
for i in range(2**(n-1)):#1番目は確定だから
    cnt=0
    s=0
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            s+=cost[j+1]
            s+=max(a[j+1],h+cnt)-a[j+1]
    if cnt==k-1:
        ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
from itertools import combinations
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 10**9*15
for i in list(combinations(range(2,N+1),K-1)):#2番~N番からK-1個選ぶ
    B = copy.copy(A)
    count = 0
    C = sorted(i)#組み合わせをソート
    print(C)
    for j in C:
        while max(B[0:j-1]) >= B[j-1]:#シフト量+2番のビルが1番:B[0]~シフト量+1番:B[k]のビルより高く
            B[j-1] += 1#シフト量+2番目のビルを伸ばす
            count += 1#コストをプラス
    ans = min(ans,count)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

bound = [0] * N
bound[0] = A[0]
for i in range(1, N):
    bound[i] = max(bound[i - 1], A[i])
bound[0] = 0

ans = 10 ** 18
for bit in range(1 << N):
    #check k
    count = 0
    for i in range(N):
        if bit & 1 << i > 0:
            count += 1
    if count < K:
        continue

    cost = 0
    h = -1
    for i in range(N):
        if bit & 1 << i > 0:
            if h == -1 and bound[i] >= A[i]:
                cost += bound[i] - A[i] + 1
                h = bound[i] + 1
            elif A[i] <= bound[i] or A[i] <= h:
                x = max(bound[i], h)
                cost += x - A[i] + 1
                h = x + 1
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

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

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
      else:
        prevh=a[j+1]
    else:
      prevh=a[j+1]
  ans=min(ans,cost)
  #print("ans",ans)
print(ans)

Submission status: Wrong Answer

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

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  print("cnt i",i)
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        print("cost",j,cost)
      else:
        prevh=a[j+1]
  ans=min(ans,cost)
  #print("ans",ans)
print(ans)

Submission status: Wrong Answer

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

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
      else:
        prevh=a[j+1]
  ans=min(ans,cost)
  #print("ans",ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001001001
bt=[]

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prev=0
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
        prev=j+1
      else:
        prevh=a[j+1]
        prev=j+1
  ans=min(ans,cost)
  #print("ans",ans)
if n==1 and k==1:
  ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001001001
bt=[]

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prev=0
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
        prev=j+1
  ans=min(ans,cost)
  #print("ans",ans)
if n==1 and k==1:
  ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001001001
bt=[]

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prev=0
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
        prev=j+1
  ans=min(ans,cost)
  #print("ans",ans)
if n==1 and k==1:
  ans=a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001001001
bt=[]

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prev=0
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
        prev=j+1
  ans=min(ans,cost)
  #print("ans",ans)
if n==1 and k==1:
  ans=a[-1]
print(ans)
print("")

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001
bt=[]

for i in range(1<<n-1):
  cnt=0
  cost=0
  tmp=[]
  for j in range(n):
    if 1<<j & i:
      cnt+=1

  if cnt==k-1:
    #print("cnt i",i)
    prev=0
    prevh=a[0]
    for j in range(n-1):
      if 1<<j & i:
        if prevh>a[j+1]:
          cost+=prevh+1-a[j+1]
          prevh+=1
          #print("cost",j,cost)
          prev=j+1
    ans=min(ans,cost)
    #print("ans",ans)
if n==1 and k==1:
  ans=a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001
b=[0 for i in range(n)]

for i in range(1<<n-1):
  for l in range(n):
    b[l]=a[l]
  cnt=0
  cost=0
  for j in range(n):
    if 1<<j & i:
      cnt+=1

  if cnt==k-1:
    #print("cnt i",i)
    prev=0
    for j in range(n-1):
      if 1<<j & i:
        if b[prev]>b[j+1]:
          cost+=b[prev]+1-b[j+1]
          b[j+1]=b[prev]+1
          #print("cost",j,cost)
          prev=j
    ans=min(ans,cost)
    #print("ans",ans)
if n==1 and k==1:
  ans=a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001
b=[]
for i in a:
  b.append(i)
for i in range(1<<n):
  for l in range(n):
    b[l]=a[l]
  cnt=0
  cost=0
  for j in range(1,n):
    if 1<<j & i:
      cnt+=1

  if cnt==k-1:
    #print("cnt i",i)
    prev=0
    for j in range(1,n):
      if 1<<j & i:
        if b[prev]>b[j]:
          cost+=b[prev]+1-b[j]
          b[j]=b[prev]+1
          #print("cost",cost)
          prev=j
    ans=min(ans,cost)
    #print("ans",ans)
if n==1 and k==1:
  ans=a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=1001001001001
b=[]
for i in a:
  b.append(i)
for i in range(1<<n):
  for l in range(n):
    b[l]=a[l]
  cnt=0
  cost=0
  for j in range(1,n):
    if 1<<j & i:
      cnt+=1

  if cnt==k-1:
    #print("cnt i",i)
    prev=0
    for j in range(1,n):
      if 1<<j & i:
        if b[prev]>b[j]:
          cost+=b[prev]+1-b[j]
          b[j]=b[prev]+1
          #print("cost",cost)
          prev=j
    ans=min(ans,cost)
    #print("ans",ans)
print(ans)

Submission status: Wrong Answer

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

highest = [A[0]]#その建物までの中で一番高いもの
for i in range(1,len(A)):
    highest.append(max(A[i],highest[i-1]))

#print(A)
#print(highest)
#print()

ans = float('inf')
for status in range(1<<N):
    bdg = []
    for mask in range(N):
        if (1<<mask)&status:
            bdg.append(mask)
    if len(bdg) != K:
        continue
    
    if A[bdg[0]] < highest[bdg[0]]:
        continue
    
    tmp = 0
    std = A[bdg[0]]+1
    #print(bdg)
    for i in range(1,len(bdg)):
        #print("std",std)
        #print("bdg[i]",A[bdg[i]])
        if A[bdg[i]] >= std:#元から基準値より高いとき
            std = max(A[bdg[i]],highest[bdg[i]-1])
        else:
            #print("wannabe",std)
            #print("add",std-A[bdg[i]])
            tmp += max(highest[bdg[i]-1], std) - A[bdg[i]]
        std += 1
        #print("$$$$$$$$$$$$$")
    
    #print("tmp",tmp)
    #print('####################################')
    ans = min(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

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

highest = [A[0]]#その建物までの中で一番高いもの
for i in range(1,len(A)):
    highest.append(max(A[i],highest[i-1]))

#print(highest)

ans = float('inf')
for status in range(1<<N):
    bdg = []
    for mask in range(N):
        if (1<<mask)&status:
            bdg.append(mask)
    if len(bdg) != K:
        continue
    
    if A[bdg[0]] < highest[bdg[0]]:
        continue
    
    tmp = 0
    std = A[bdg[0]]+1
    #print(bdg)
    for i in range(1,len(bdg)):
        #print("std",std)
        #print("bdg[i]",A[bdg[i]])
        if A[bdg[i]] >= std:#元から基準値より高いとき
            std = max(A[bdg[i]],highest[bdg[i]])
        else:
            #print("wannabe",std)
            #print("add",std-A[bdg[i]])
            tmp += max(highest[bdg[i]], std) - A[bdg[i]]
        std += 1
        #print("$$$$$$$$$$$$$")
    
    #print("tmp",tmp)
    #print('####################################')
    ans = min(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

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

highest = [A[0]]#その建物までの中で一番高いもの
for i in range(1,len(A)):
    highest.append(max(A[i],highest[i-1]))

#print(highest)

ans = float('inf')
for status in range(1<<N):
    bdg = []
    for mask in range(N):
        if (1<<mask)&status:
            bdg.append(mask)
    if len(bdg) != K:
        continue
    
    if A[bdg[0]] < highest[bdg[0]]:
        continue
    
    tmp = 0
    std = A[bdg[0]]
    plus = 1
    #print(bdg)
    for i in range(1,len(bdg)):
        if A[bdg[i]] > std:
            plus = 1
            std = max(A[bdg[i]],highest[bdg[i]])
        else:
            tmp += max(highest[bdg[i]],(std+plus)) - A[bdg[i]]
            plus += 1
    
    #print("tmp",tmp)
    #print('####################################')
    ans = min(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

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

highest = [A[0]]#その建物までの中で一番高いもの
for i in range(1,len(A)):
    highest.append(max(A[i],highest[i-1]))

ans = float('inf')
for status in range(1<<N):
    bdg = []
    for mask in range(N):
        if (1<<mask)&status:
            bdg.append(mask)
    if len(bdg) != K:
        continue
    
    tmp = 0
    std = A[bdg[0]]
    plus = 1
    #print(bdg)
    if A[bdg[0]] < highest[bdg[0]-1]:
        continue
    for i in range(1,len(bdg)):
        if A[bdg[i]] > std:
            plus = 1
            std = A[bdg[i]]
        else:
            tmp += (std+plus) - A[bdg[i]]
            plus += 1
    
    #print("tmp",tmp)
    #print('####################################')
    ans = min(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

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

highest = [A[0]]#その建物までの中で一番高いもの
for i in range(1,len(A)):
    highest.append(max(A[i],highest[i-1]))

ans = float('inf')
for status in range(1<<N):
    bdg = []
    for mask in range(N):
        if (1<<mask)&status:
            bdg.append(mask)
    if len(bdg) != K:
        continue
    
    tmp = 0
    std = A[bdg[0]]
    plus = 1
    #print(bdg)
    if A[bdg[0]] < highest[bdg[0]]:
        continue
    for i in range(1,len(bdg)):
        if A[bdg[i]] > std:
            plus = 1
            std = A[bdg[i]]
        else:
            tmp += (std+plus) - A[bdg[i]]
            plus += 1
    
    #print("tmp",tmp)
    #print('####################################')
    ans = min(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
#n = int(input())
n, k = map(int, sys.stdin.readline().split())
#n = input()
a = list(map(int, sys.stdin.readline().split()))

l = list(itertools.combinations(range(n), k))

ans = 10 ** 18
for i in range(len(l)):
    cost = 0
    m1 = 0
    p = 20
    for j in range(l[i][0]+1):
        if a[j] > m1:
            m1 = a[j]
            p = j

        if j == l[i][0]:
            if m1 == a[j]:
                if p != j:
                    cost += 1
            else:
                cost += (m1 - a[j] + 1)

    
    r = 1
    if len(l[0]) >= 2:
        q = l[i][r]
    else:
        q = 20

    m2 = a[l[i][0]] + cost

    for j in range(l[i][0]+1, n):
        if j == q:
            if a[j] > m2:
                m2 = a[j]
            else:
                m2 += 1
                cost += (m2 - a[j])

            if r != len(l[0])-1:
                r += 1
                q = l[i][r]
            
        else:
            if a[j] > m2:
                cost += a[j] - m2
                m2 = a[j]
                

    if cost < ans:
        ans = cost


print(ans)
print()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
#n = int(input())
n, k = map(int, sys.stdin.readline().split())
#n = input()
a = list(map(int, sys.stdin.readline().split()))

l = list(itertools.combinations(range(n), k))
print(a)
print(l)

ans = 10 ** 18
for i in range(len(l)):
    cost = 0
    m1 = 0
    p = 20
    for j in range(l[i][0]+1):
        if a[j] > m1:
            m1 = a[j]
            p = j

        if j == l[i][0]:
            if m1 == a[j]:
                if p != j:
                    cost += 1
            else:
                cost += (m1 - a[j] + 1)

    
    r = 1
    if len(l[0]) >= 2:
        q = l[i][r]
    else:
        q = 20

    m2 = a[l[i][0]] + cost

    for j in range(l[i][0]+1, n):
        if j == q:
            if a[j] > m2:
                m2 = a[j]
            else:
                m2 += 1
                cost += (m2 - a[j])

            if r != len(l[0])-1:
                r += 1
                q = l[i][r]
            
        else:
            if a[j] > m2:
                cost += a[j] - m2
                m2 = a[j]
                

    if cost < ans:
        ans = cost


print(ans)
print()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
#n = int(input())
n, k = map(int, sys.stdin.readline().split())
#n = input()
a = list(map(int, sys.stdin.readline().split()))

l = list(itertools.combinations(range(n), k))
print(a)
print(l)

ans = 10 ** 18
for i in range(len(l)):
    cost = 0
    m1 = 0
    p = 20
    for j in range(l[i][0]+1):
        if a[j] > m1:
            m1 = a[j]
            p = j

        if j == l[i][0]:
            if m1 == a[j]:
                if p != j:
                    cost += 1
            else:
                cost += (m1 - a[j] + 1)

    
    r = 1
    if len(l[0]) >= 2:
        q = l[i][r]
    else:
        q = 20

    m2 = a[l[i][0]] + cost

    for j in range(l[i][0]+1, n):
        if j == q:
            if a[j] > m2:
                m2 = a[j]
            else:
                m2 += 1
                cost += (m2 - a[j])

            if r != len(l[0])-1:
                r += 1
                q = l[i][r]
            
        else:
            if a[j] > m2:
                cost += a[j] - m2
                m2 = a[j]
                

    if cost < ans:
        ans = cost


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    # print(building)
    
    ans = 10 ** 15
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        #print(bin(i),p_b) 

        tmp_ans = 0
        max_h = p_b[0]
        for j in range(1,k):
            if max_h < p_b[j]:
                max_h = p_b[j]
                continue
            else:
                tmp_ans += 1 + max_h - p_b[j]
                max_h += 1
        #print(tmp_ans)
        else:
            ans = min(ans,tmp_ans)

    print(ans) 

if __name__ == "__main__":
    slove()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    # print(building)
    
    ans = 10 ** 12
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        #print(bin(i),p_b) 

        tmp_ans = 0
        max_h = p_b[0]
        for j in range(1,k):
            if max_h < p_b[j]:
                max_h = p_b[j]
                continue
            else:
                tmp_ans += 1 + max_h - p_b[j]
                max_h += 1
        #print(tmp_ans)
        else:
            ans = min(ans,tmp_ans)

    print(ans) 

if __name__ == "__main__":
    slove()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    # print(building)
    
    ans = 10 ** 12
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        #print(bin(i),p_b) 

        tmp_ans = 0
        for j in range(k-1):
            if p_b[j] < p_b[j+1]:
                continue
            else:
                tmp_ans += 1 + p_b[j] - p_b[j+1]
                p_b[j+1] = 1 + p_b[j]
        #print(tmp_ans)
        else:
            ans = min(ans,tmp_ans)

    print(ans) 

if __name__ == "__main__":
    slove()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    # print(building)
    
    ans = -1
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        #print(bin(i),p_b) 

        tmp_ans = 0
        for j in range(k-1):
            if p_b[j] < p_b[j+1]:
                continue
            else:
                tmp_ans += 1 + p_b[j] - p_b[j+1]
                p_b[j+1] = 1 + p_b[j]
        #print(tmp_ans)

        if ans < 0:
            ans = tmp_ans
        else:
            ans = min(ans,tmp_ans)

    print(ans) 

if __name__ == "__main__":
    slove()

Submission status: Wrong Answer

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

cost = 10 ** 18
for i in range(2 ** (n - 1)):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if i >> j & 1:
            if a[j + 1] <= prev:
                c += prev - a[j + 1] + 1
                prev += 1
            else:
                prev = a[j + 1]
            num += 1
    if num >= k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

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

cost = 10 ** 18
for i in range(2 ** (n - 1)):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if num == k - 1:
            break
        if i >> j & 1:
            if a[j + 1] <= prev:
                c += prev - a[j + 1] + 1
                prev += 1
            else:
                prev = a[j + 1]
            num += 1
    if num == k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

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

cost = 10 ** 9 * n + 1
for i in range(1, 2 ** (n - 1)):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if num == k - 1:
            break
        if (i >> j & 1) and a[j + 1] <= prev:
            c += prev - a[j + 1] + 1
            prev = prev + 1
            num += 1
        elif (i >> j & 1) and a[j + 1] > prev:
            prev = a[j + 1]
            num += 1
    if num == k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

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

cost = 10 ** 9 * n + 1
for i in range(1, 2 ** n):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if num == k - 1:
            break
        if (i >> j & 1) and a[j + 1] <= prev:
            c += prev - a[j + 1] + 1
            prev = prev + 1
            num += 1
        elif (i >> j & 1) and a[j + 1] > prev:
            prev = a[j + 1]
            num += 1
    if num == k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

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

cost = 10 ** 9 * n + 1
for i in range(1, 2 ** n):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if num == k - 1:
            break
        if (i >> j & 1) and a[j + 1] <= prev:
            c += prev - a[j + 1] + 1
            prev = prev + 1
            num += 1
        elif (i >> j & 1) and a[j + 1] > prev:
            print(a[j + 1])
            prev = a[j + 1]
            num += 1
    if num == k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

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

cost = 10 ** 9 * n + 1
for i in range(1, 2 ** (n - 1)):
    num = 0
    for j in range(n):
        if i >> j & 1:
           num += 1
    if  num != k - 1:
        continue
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if (i >> j & 1) and a[j + 1] <= prev:
            c += prev - a[j + 1] + 1
            prev = prev + 1
    if c != 0:
        cost = min(c, cost)
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K,*A= map(int, read().split())
l = [i for i in range(1,N)]
cost = float('inf')
for B in itertools.combinations(l,K-1):
  ans = 0
  pre = A[0]
  for i in B:
    if pre < A[i]:
      pre = A[i]
    else:
      ans += pre-A[i]+1
      pre +=1
  cost = min(ans,cost)
print(cost)

Submission status: Wrong Answer

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

Solution code:
import itertools


N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf')  


for pattern in itertools.combinations(range(1,N),K-1):
    temp_cost = 0
    temp_pattern = [0] + list(pattern)
    max_high = a[0]

    for i in range(1,N):
        if i in temp_pattern:
            diff = a[i]- max_high
            if diff ==  0:
                temp_cost += 1
            elif diff < 0 :
                temp_cost += ( max_high - a[i] ) + 1
                max_high = max_high +1
            else:
                temp_cost += 0
                max_high = a[i]
        else:
            max_high = max (a[i] ,max_high)

    ans = min(ans, temp_cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy

N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf')  
for pattern in itertools.combinations(range(1,N),K-1):
    temp_cost = 0
    temp_pattern = [0] + list(pattern)
    max_high = a[0]

    for i in range(N):
        max_high = max (a[i] ,max_high)
        if i in temp_pattern:
            if a[i]- max_high ==  0:
                temp_cost += 0
            else:
                temp_cost += ( max_high - a[i] ) + 1
                max_high = max_high +1
            
    ans = min(ans, temp_cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import copy

N, K = map(int, input().split())
a = list(map(int, input().split()))
temp_a = copy.copy(a)
ans = float('inf')


#combinationは昇順ででてくる
for pattern in itertools.combinations(range(1,N),K-1):
    temp_cost = 0
    temp_pattern = [0] + list(pattern)
    temp_a = copy.copy(a)
    for i in range(K-1):
        diff = temp_a[temp_pattern[i]] - temp_a[temp_pattern[i+1]]
        if diff >=  0:
            temp_a[temp_pattern[i+1]] += diff + 1
            temp_cost += diff + 1
    
    ans = min(ans, temp_cost)

print(ans)