Problem:


Score : 300 points

Problem Statement

You have N bamboos. The lengths (in centimeters) of these are l_1, l_2, ..., l_N, respectively.

Your objective is to use some of these bamboos (possibly all) to obtain three bamboos of length A, B, C. For that, you can use the following three kinds of magics any number:

Extension Magic: Consumes 1 MP (magic point). Choose one bamboo and increase its length by 1.

Shortening Magic: Consumes 1 MP. Choose one bamboo of length at least 2 and decrease its length by 1.

Composition Magic: Consumes 10 MP. Choose two bamboos and combine them into one bamboo. The length of this new bamboo is equal to the sum of the lengths of the two bamboos combined. (Afterwards, further magics can be used on this bamboo.)

At least how much MP is needed to achieve the objective?

Constraints

3 \leq N \leq 8

1 \leq C < B < A \leq 1000

1 \leq l_i \leq 1000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B C
l_1
l_2
:
l_N

Output

Print the minimum amount of MP needed to achieve the objective.

Sample Input 1

5 100 90 80
98
40
30
21
80

Sample Output 1

23

We are obtaining three bamboos of lengths 100, 90, 80 from five bamboos 98, 40, 30, 21, 80. We already have a bamboo of length 80, and we can obtain bamboos of lengths 100, 90 by using the magics as follows at the total cost of 23 MP, which is optimal.

Use Extension Magic twice on the bamboo of length 98 to obtain a bamboo of length 100. (MP consumed: 2)

Use Composition Magic on the bamboos of lengths 40, 30 to obtain a bamboo of length 70. (MP consumed: 10)

Use Shortening Magic once on the bamboo of length 21 to obtain a bamboo of length 20. (MP consumed: 1)

Use Composition Magic on the bamboo of length 70 obtained in step 2 and the bamboo of length 20 obtained in step 3 to obtain a bamboo of length 90. (MP consumed: 10)

Sample Input 2

8 100 90 80
100
100
90
90
90
80
80
80

Sample Output 2

0

If we already have all bamboos of the desired lengths, the amount of MP needed is 0. As seen here, we do not necessarily need to use all the bamboos.

Sample Input 3

8 1000 800 100
300
333
400
444
500
555
600
666

Sample Output 3

243



Sample input:
5 100 90 80
98
40
30
21
80


Sample output:
23

Submission status: Time Limit Exceeded

Solution code:

from itertools import combinations
from copy import deepcopy

class Kadomatsu:
  def __init__(self, length, cost):
    self.length = length
    self.cost = cost

  def synthesize(self, kadomatsu):
    length = self.length + kadomatsu.length
    cost = self.cost + kadomatsu.cost + 10
    return Kadomatsu(length, cost)
  
  def __str__(self):
    return "Kadomatsu(length={0}, cost={1})".format(self.length, self.cost)
  
  def __repr__(self):
    return self.__str__()

def parse():
  N, A, B, C = map(int, input().split(" "))
  L = []
  for n in range(N):
    L.append(int(input()))
  return N, A, B, C, L

def main():
  N, A, B, C, L = parse()
  # print(N, A, B, C, L)

  # 門松セットの初期化
  kadomatsu_set_list = []
  kadomatsu_set = []
  for l in L:
    kadomatsu_set.append(Kadomatsu(l, 0))
  kadomatsu_set_list.append(kadomatsu_set)
  # print(kadomatsu_set_list)

  # kadomatsu_set_list > 3の時，合成可能なので，
  # 合成可能な場合，合成を繰り返す
  i = 0
  while len(kadomatsu_set_list[i]) > 3:
    for combination in combinations(kadomatsu_set_list[i], 2):
      # print("combination:", combination)
      new_kadomastu = combination[0].synthesize(combination[1])
      
      # 一旦削除
      # kadomatsu_set_list[i].remove(combination[0])
      # kadomatsu_set_list[i].remove(combination[1])
      
      # new_kadomastu_setの初期化
      new_kadomastu_set = []
      for kadomatsu in kadomatsu_set_list[i]:
        if kadomatsu is combination[0] or kadomatsu is combination[1]: continue
        new_kadomastu_set.append(kadomatsu)
      new_kadomastu_set.append(new_kadomastu)
      # print("new_kadomastu_set:", new_kadomastu_set)
      # input()
      kadomatsu_set_list.append(new_kadomastu_set)

      # 削除したものを元に戻す
      # kadomatsu_set_list[i].append(combination[0])
      # kadomatsu_set_list[i].append(combination[1])
      # print("kadomatsu_set_list[i]:", kadomatsu_set_list[i])
      # input()
    # exit(0)
    i += 1
  
  # print(len(kadomatsu_set_list))
  min_cost = 10 ** 20
  for kadomatsu_set in kadomatsu_set_list:
    # print(kadomatsu_set)

    # Aに最も長さが近い門松を探す
    min_diff_A = 10 ** 10
    min_diff_A_i = 0
    for i, kadomatsu in enumerate(kadomatsu_set):
      diff = abs(A - kadomatsu.length)
      if min_diff_A > diff:
        min_diff_A = diff
        min_diff_A_i = i

    # Bに最も長さが近い門松を探す
    min_diff_B = 10 ** 10
    min_diff_B_i = 0
    for i, kadomatsu in enumerate(kadomatsu_set):
      if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
      diff = abs(B - kadomatsu.length)
      if min_diff_B > diff:
        min_diff_B = diff
        min_diff_B_i = i
    
    # Cに最も長さが近い門松を探す
    min_diff_C = 10 ** 10
    min_diff_C_i = 0
    for i, kadomatsu in enumerate(kadomatsu_set):
      if i == min_diff_A_i: continue  # Aですでに選んでいる門松はスキップ
      if i == min_diff_B_i: continue  # Bですでに選んでいる門松はスキップ
      diff = abs(C - kadomatsu.length)
      if min_diff_C > diff:
        min_diff_C = diff
        min_diff_C_i = i
    
    cost = min_diff_A + min_diff_B + min_diff_C \
      + kadomatsu_set[min_diff_A_i].cost + kadomatsu_set[min_diff_B_i].cost + kadomatsu_set[min_diff_C_i].cost
    if min_cost > cost: min_cost = cost
    # print(min_diff_A_i, min_diff_B_i, min_diff_C_i, cost)
    # input()
  print(min_cost)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
def input(): return sys.stdin.readline().strip()

"""
この関数、xxxxxxxxxをaaabbbcccやaabbbbbbcみたいに分けるのには使えるけど
abcabcabcみたいに入り混じった場合が出てこないからだめだ。。。

def func(n): # 和がnになるような３つの数字の組を全列挙
    arr = []
    for i in range(1, n - 1):
        for j in range(1, n - i):
            arr.append((i, j, (n - i - j)))
    return arr
"""

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + [n%b]
    return [n%b]

def main():
    N, A, B, C = map(int, input().split())
    L = [int(input()) for _ in range(N)]

    """
    どの竹をくっつけるかをビット全探索
    """

    ans = 10**100
    for n in range(1 << N):
        bumboo_num = [i for i in range(N) if n & (1 << i)] # まずは使う竹の選別
        l = len(bumboo_num)
        for i in range(3 **l): # 各竹をA, B, Cのどれに振り分けるかの3^l通りを試すべきだった
            near_a = 0
            near_b = 0
            near_c = 0
            p = 0
            q = 0
            r = 0
            x = base10to(i, 3)
            l_x = len(x)
            for j in range(l):
                if l_x - j - 1 < 0 or x[l_x - j - 1] == 0:
                    p += 1
                    near_a += L[bumboo_num[j]]
                elif l_x - j - 1 < 0 or x[l_x - j - 1] == 1:
                    q += 1
                    near_b += L[bumboo_num[j]]
                elif l_x - j - 1 < 0 or x[l_x - j - 1] == 2:
                    r += 1
                    near_c += L[bumboo_num[j]]
            if p == 0 or q == 0 or r == 0: continue
            val = 10 * (p - 1 + q - 1 + r - 1)
            val1 = val + abs(A - near_a) + abs(B - near_b) + abs(C - near_c)
            #if ans > val1: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], p, q, r, val1))
            ans = min(ans, val1)
            val2 = val + abs(A - near_a) + abs(C - near_b) + abs(B - near_c)
            #if ans > val2: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], p, r, q, val2))
            ans = min(ans, val2)
            val3 = val + abs(B - near_a) + abs(A - near_b) + abs(C - near_c)
            #if ans > val3: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], q, p, r, val3))
            ans = min(ans, val3)
            val4 = val + abs(B - near_a) + abs(C - near_b) + abs(A - near_c)
            #if ans > val4: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], r, p, q, val4))
            ans = min(ans, val4)
            val5 = val + abs(C - near_a) + abs(A - near_b) + abs(B - near_c)
            #if ans > val5: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], q, r, p, val5))
            ans = min(ans, val5)
            val6 = val + abs(C - near_a) + abs(B - near_b) + abs(A - near_c)
            #if ans > val6: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], r, q, p, val6))
            ans = min(ans, val6)
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
def input(): return sys.stdin.readline().strip()

"""
この関数、xxxxxxxxxをaaabbbcccやaabbbbbbcみたいに分けるのには使えるけど
abcabcabcみたいに入り混じった場合が出てこないからだめだ。。。

def func(n): # 和がnになるような３つの数字の組を全列挙
    arr = []
    for i in range(1, n - 1):
        for j in range(1, n - i):
            arr.append((i, j, (n - i - j)))
    return arr
"""

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

def main():
    N, A, B, C = map(int, input().split())
    L = [int(input()) for _ in range(N)]

    """
    どの竹をくっつけるかをビット全探索
    """

    ans = 10**100
    for n in range(1 << N):
        bumboo_num = [i for i in range(N) if n & (1 << i)] # まずは使う竹の選別
        l = len(bumboo_num)
        for i in range(3 **l): # 各竹をA, B, Cのどれに振り分けるかの3^l通りを試すべきだった
            near_a = 0
            near_b = 0
            near_c = 0
            p = 0
            q = 0
            r = 0
            x = base10to(i, 3)
            l_x = len(x)
            for j in range(l):
                if l_x - j - 1 < 0 or x[l_x - j - 1] == '0':
                    p += 1
                    near_a += L[bumboo_num[j]]
                elif l_x - j - 1 < 0 or x[l_x - j - 1] == '1':
                    q += 1
                    near_b += L[bumboo_num[j]]
                elif l_x - j - 1 < 0 or x[l_x - j - 1] == '2':
                    r += 1
                    near_c += L[bumboo_num[j]]
            if p == 0 or q == 0 or r == 0: continue
            val = 10 * (p - 1 + q - 1 + r - 1)
            val1 = val + abs(A - near_a) + abs(B - near_b) + abs(C - near_c)
            #if ans > val1: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], p, q, r, val1))
            ans = min(ans, val1)
            val2 = val + abs(A - near_a) + abs(C - near_b) + abs(B - near_c)
            #if ans > val2: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], p, r, q, val2))
            ans = min(ans, val2)
            val3 = val + abs(B - near_a) + abs(A - near_b) + abs(C - near_c)
            #if ans > val3: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], q, p, r, val3))
            ans = min(ans, val3)
            val4 = val + abs(B - near_a) + abs(C - near_b) + abs(A - near_c)
            #if ans > val4: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], r, p, q, val4))
            ans = min(ans, val4)
            val5 = val + abs(C - near_a) + abs(A - near_b) + abs(B - near_c)
            #if ans > val5: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], q, r, p, val5))
            ans = min(ans, val5)
            val6 = val + abs(C - near_a) + abs(B - near_b) + abs(A - near_c)
            #if ans > val6: print("n={}, p={}, q={}, r={}, val={}".format(bin(n)[2:], r, q, p, val6))
            ans = min(ans, val6)
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_min_mp_without_merge(seq, a, b, c):
        '合成魔法を使わずに seq の要素を作り出すのに必要な最小 MP を求める (O(xP3) = O(x^3))'
        ans = inf
        n = len(seq)
        for pattern in permutations(range(n), r=3):
            i, j, k = pattern
            ans = min(ans, abs(seq[i] - a) + abs(seq[j] - b) + abs(seq[k] - c))
        # print(f"seq {seq} ans {ans}")
        return ans
        


    def calc_min_mp(L, a, b, c):
        'ちょうど i 回合成魔法を使い i+1 個の L の要素を合体するとき、a, b, c の長さを作り出すのに必要な最小 MP を求める'
        ans = calc_min_mp_without_merge(L, a, b, c)
        n = len(L)
        if n > 3:
            for merge_pattern in combinations(range(n), r=2):
                new_seq = [L[ind] for ind in range(n) if ind not in merge_pattern]
                new_bamboo = sum([L[ind] for ind in merge_pattern])
                new_seq.append(new_bamboo)
                ans = min(ans, calc_min_mp(new_seq, a, b, c) + 10)
        return ans

    
    
    n, a, b, c = mi()
    L = [ii() for _ in range(n)]

    print(calc_min_mp(L, a, b, c))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]

ans = float('inf')
for Lp in itertools.permutations(L):
    Lac = tuple(itertools.accumulate(([0] + list(Lp))))
    for a in range(1, N - 1):
        for b in range(a + 1, N):
            for c in range(b + 1, N + 1):
                A_MP = 10 * (a - 1) + abs(Lac[a] - Lac[0] - A)
                B_MP = 10 * (b - a - 1) + abs(Lac[b] - Lac[a] - B)
                C_MP = 10 * (c - b - 1) + abs(Lac[c] - Lac[b] - C)
                ans = min(ans, A_MP + B_MP + C_MP)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]
value=10**10
itelst=[list(permutations(L,i)) for i in range(3,N+1)]
for a,b,c in list(permutations([A,B,C])):
    for n in range(N-2):
        for lst in itelst[n]:
            for i1 in range(1,len(lst)-1):
                for i2 in range(i1+1,len(lst)):
                    value=min(value, (len(lst)-3)*10+\
                            round(abs(a-sum(lst[  :i1])))+\
                            round(abs(b-sum(lst[i1:i2])))+\
                            round(abs(c-sum(lst[i2:  ]))))

print(value)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
#A.sort();B.sort();C.sort()
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])!=len((set(A[i][1]+B[j][1]+C[k][1]))):
                continue
            else:
                #print(A[i][1]+B[j][1]+C[k][1])
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
A.sort();B.sort();C.sort()
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])!=len((set(A[i][1]+B[j][1]+C[k][1]))):
                continue
            else:
                #print(A[i][1]+B[j][1]+C[k][1])
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

list = [int(i) for i in input().rstrip().split(" ")]

matsu_count = list[0]
require = sorted(list[1:])

matsu_list = sorted([int(input().rstrip()) for i in range(matsu_count)])

def get_mp(matsu:list):
    ans = 0
    for i in range(3):
        ans += abs(matsu[i] - require[i])
    return ans

def get_ans(matsu:list):
    if len(matsu) == 3:
        return get_mp(matsu)
    ans = 80000
    for i in range(len(matsu) - 3 + 1):
        ans = min(ans, get_mp(matsu[i:]))
    for i in range(len(matsu)):
        for j in range(i + 1, len(matsu)):
            sub_matsu = []
            for k in range(len(matsu)):
                if k == i or k == j:
                    continue
                else:
                    sub_matsu.append(matsu[k])
            sub_matsu.append(matsu[i] + matsu[j])
            ans = min(ans, get_ans(sorted(sub_matsu)) + 10)


    return ans

ans = get_ans(matsu_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    #key = str((index, current_ch, sss, used, costs))
    key = str((index, current_ch, sss, used, (len(costs['a']), sum(costs['a'])), (len(costs['b']), sum(costs['b'])), (len(costs['c']), sum(costs['c']))))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.01:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c = list(map(int, input().split(' ')))
l = []
d = {'a': a, 'b': b, 'c': c}
for i in range(n):
    l.append(int(input()))
l = sorted(l)[::-1]
seed = {
	3: [[1,1,1]],
	4: [[1,1,2], [1,2,1], [2,1,1]], # mp=10
	5: [[1,1,3], [1,3,1], [3,1,1],  # mp=20
        [1,2,2], [2,1,2], [2,2,1]],
	6: [[1,1,4], [1,4,1], [4,1,1],  # mp=30
        [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1],
        [2,2,2]],
	7: [[1,1,5], [1,5,1], [5,1,1],  # mp=40
        [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1],
        [1,3,3], [3,1,3], [3,3,1],
        [2,2,3], [2,3,2], [3,2,2]],
	8: [[1,1,6], [1,6,1], [6,1,1],  # mp=50
        [1,2,5], [1,5,2], [2,1,5], [2,5,1], [5,1,2], [5,2,1],
        [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1],
        [2,2,4], [2,4,2], [4,2,2],
        [2,3,3], [3,2,3], [3,3,2]],
}
ans = 9999999

def next(ch):
    return 'b' if ch == 'a' else 'c' if ch == 'b' else 'd'
abc = ['a', 'b', 'c']
min_a = 9999999
memo = {}
def f(index, current_ch, sss, used, costs):
    global min_a
    key = str((index, current_ch, sss, used, costs))
    if key in memo:
        return memo[key]
    
    if costs['a'] and current_ch == 'b':
        if min_a >= abs(sum(costs['a']) - a):
            min_a = abs(sum(costs['a']) - a)
        elif min_a < abs(sum(costs['a']) - a) * 0.1:
            return 9999999

    if current_ch == 'd':
        memo[key] = abs(sum(costs['a']) - a) + abs(sum(costs['b']) - b) + abs(sum(costs['c']) - c)
        return memo[key]
    # if index >= n or n-index < sss[abc.index(current_ch)] - len(costs[current_ch]) + (2-abc.index(current_ch)):
    if index >= n:
        # print ('hoge', sss, costs, n, index, current_ch)
        memo[key] = 9999999
        return memo[key]
    # skip
    temp = min(9999999, f(index+1, current_ch, sss, used, costs))
    # 1つ追加
    tugihe = len(costs[current_ch]) == sss[abc.index(current_ch)] - 1
    next_ch = next(current_ch) if tugihe else current_ch
    next_index = 0 if tugihe else index + 1
    for i in range(index, n):
        if used[i]:
            continue
        used[i] = True
        costs[current_ch].append(l[i])
        temp = min(temp, f(next_index, next_ch, sss, used, costs))
        used[i] = False
        costs[current_ch].pop(len(costs[current_ch])-1)
    memo[key] = temp
    return memo[key]

for k in range(3, n+1):
  mp = (k - 3) * 10
  used = [False] * n
  for seed_k_j in seed[k]:
      hoge = f(0, 'a', seed_k_j, used, {'a':[], 'b':[], 'c':[]}) + mp
    #   if hoge < 9999999:
    #       print (hoge, seed_k_j)
      ans = min(ans, hoge)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


n, a, b, c = map(int, input().split())
L = [int(input())for _ in range(n)]
L_perm = list(itertools.permutations(L))
ans = 10**9
for l in L_perm:
    for i in range(1, n-1):
        A_tree = l[:i]
        synthesis_A = 10 * (i-1)
        fix_A = abs(a-sum(A_tree))
        for j in range(i+1, n):
            B_tree = l[i:j]
            synthesis_B = 10 * (j-i-1)
            fix_B = abs(b-sum(B_tree))
            for k in range(j+1, n+1):
                C_tree = l[j:k]
                synthesis_C = 10 * (k-j-1)
                fix_C = abs(c-sum(C_tree))

                total = fix_A + fix_B + fix_C + synthesis_A + synthesis_B + synthesis_C
                ans = min(ans, total)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++


def aaa(ll,a,b,c):
	ret=a+b+c
	for i,v1 in enumerate(ll):
		if v1==0:
			continue
		t1=abs(a-v1)
		if ret < t1:
			continue
		for j,v2 in enumerate(ll):
			if v2==0:
				continue
			if i==j:
				continue
			t2=t1 + abs(b-v2)
			if ret < t2:
				continue
			for k,v3 in enumerate(ll):
				if v3==0:
					continue
				if i==k or j==k:
					continue
				t3 = t2 + abs(c-v3)
				ret=min(ret, t3)
	return ret		
		
def main():
	n , a, b, c = map(int, input().split())
	bb=[]
	for i in range(n):
		bb.append(int(input()))
	ans=a+b+c
	for i in range(4**n-1):
		la=[]
		lb=[]
		lc=[]
		l=[]
		for j in range(n):
			sd=(i%(4 ** (j+1)))//(4**j)
			kk=bb[j]
			pp=0
			if sd == 0:
				la.append(kk)
			elif sd==1:
				lb.append(kk)
			elif sd==2:
				lc.append(kk)
			else:
				l.append(kk)
		pp=max(0,len(la)-1)+max(len(lb)-1,0)+max(0,len(lc)-1)
		l=l+[sum(la),sum(lb),sum(lc)]
		#print(l)
		ans=min(ans,aaa(l,a,b,c)+pp*10)
				
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
global ans
ans = sum([a, b, c])
def count(a_use, b_use, c_use, non_use):
  global ans
  if a_use and b_use and c_use:
    cost = abs(sum(a_use)-a)+abs(sum(b_use)-b)+abs(sum(c_use)-c) + 10*((len(a_use)-1) + (len(b_use)-1) +(len(c_use)-1) )
    ans = min(cost, ans)
  for i in range(len(non_use)):
    temp = non_use[:]
    temp.pop(i)
    use = [non_use[i]]
    count(a_use+use, b_use, c_use, temp)
    count(a_use, b_use+use, c_use, temp)
    count(a_use, b_use, c_use+use, temp)
    count(a_use, b_use, c_use, temp)
count([], [], [], l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]


def solve(X):
    if not ("1" in X and "2" in X and "3" in X):
        return 1e10

    MS = [[L[i] for i in range(N) if X[i] == j] for j in "123"]
    ret = 1e10
    ret = min(ret, solve2(MS[0], A) + solve2(MS[1], B) + solve2(MS[2], C))
    ret = min(ret, solve2(MS[0], A) + solve2(MS[2], B) + solve2(MS[1], C))
    ret = min(ret, solve2(MS[1], A) + solve2(MS[0], B) + solve2(MS[2], C))
    ret = min(ret, solve2(MS[1], A) + solve2(MS[2], B) + solve2(MS[0], C))
    ret = min(ret, solve2(MS[2], A) + solve2(MS[0], B) + solve2(MS[1], C))
    ret = min(ret, solve2(MS[2], A) + solve2(MS[1], B) + solve2(MS[0], C))
    return ret


def solve2(M, target):
    def rec(Y, target):
        # Y: [1, 0, 0]
        if len(Y) == len(M):
            if len(set(Y)) == 1 and Y[0] == 0:
                return 1e10
            sum_M = sum([M[i] for i in range(len(M)) if Y[i] == 1])
            return abs(target - sum_M) + 10 * (Y.count(1) - 1)
        return min(rec(Y + [0], target), rec(Y + [1], target))
    ret = rec([], target)
    return ret


ans = 1e10


def rec(X):
    global ans
    if len(X) == N:
        ans = min(ans, solve(X))
        return
    rec(X + "1")
    rec(X + "2")
    rec(X + "3")


rec("")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from fractions import gcd
from functools import lru_cache, reduce

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, A, B, C = list(map(int, sys.stdin.readline().split()))
L = [int(sys.stdin.readline()) for _ in range(N)]

L = np.array(L)

# 全部試す
choosing = list(itertools.product([0, 1, 2, 3], repeat=N))
# 0: 選ばない
# 1: 竹 A にする
# 2: 竹 B にする
# 3: 竹 C にする
ans = INF
for choose in np.array(choosing):
    a = L[choose == 1]
    b = L[choose == 2]
    c = L[choose == 3]
    if len(a) == 0 or len(b) == 0 or len(c) == 0:
        continue
    s = 0
    s += abs(A - a.sum()) + (len(a) - 1) * 10
    s += abs(B - b.sum()) + (len(b) - 1) * 10
    s += abs(C - c.sum()) + (len(c) - 1) * 10
    ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getMP(L,A,B,C):
    n = len(L)
    if n == 3:
        a = abs(L[0]-A) + abs(L[1]-B) + abs(L[2]-C)
        b = abs(L[0]-A) + abs(L[2]-B) + abs(L[1]-C)
        c = abs(L[1]-A) + abs(L[0]-B) + abs(L[2]-C)
        d = abs(L[1]-A) + abs(L[2]-B) + abs(L[0]-C)
        e = abs(L[2]-A) + abs(L[0]-B) + abs(L[1]-C)
        f = abs(L[2]-A) + abs(L[1]-B) + abs(L[0]-C)
        return min(a,b,c,d,e,f)
    else:
        ans = 10**7
        for i in range(n):
            M = L + []
            M.pop(i)
            ans = min(ans, getMP(M,A,B,C))
            for j in range(n-i-1):
                M = L + []
                m = M.pop(i)
                M[j+i] += m
                ans = min(ans, getMP(M,A,B,C)+10)
        return ans
    
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]

print(getMP(L,A,B,C))

Submission status: Time Limit Exceeded

Solution code:
import itertools 
def take_solve(take):
    result=float("inf")
    for x,y,z in itertools.permutations(take):
        result=min(result,abs(x-a)+abs(y-b)+abs(z-c))
    return result
 
n,a,b,c=[int(x) for x in input().split()]
l=[]
for _ in range(n):
    l.append(int(input()))
from collections import defaultdict
d=defaultdict(int)
def ans(takes):
    takes=sorted(takes)
    key=str(takes)
    if key in d.keys():
        return d[key]
    m=len(takes)
    result=float("inf")
    if m==3:
        result=min(result,take_solve(takes)+10*(n-m))
    else:
        for i,j in itertools.combinations(list(range(m)),2):
            next_take=[takes[x] for x in range(m) if not x in (i,j)]
            next_take.append(takes[i]+takes[j])
            result=min(result,ans(next_take))
        for i,j,k in itertools.combinations(list(range(m)),3):
            result=min(result,take_solve((takes[i],takes[j],takes[k]))+10*(n-m))
    d[key]=result
    return result
print(ans(l))