Problem:


	MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

ぼくのかんがえたさいきょうのおふとん

あなたは新生活に備え，おふとんを N 枚買った．
i 番目のおふとんは si のぬくもり供給力をもつ．
これから M 日間の気温の予測から，j 日目には dj のぬくもり需要が予想される．
ぬくもりが足りなくても多すぎても快適さが損なわれるので，j 日目に掛けているおふとんのぬくもり供給力の総和と dj の差の絶対値を j 日目の不快度と呼ぶことにする．
このM 日分の不快度の合計ができるだけ少なくなるようにしたい．

ところで，あなたの部屋は残念ながらとても狭く，ベッドと押入れしかない．
そのため，ベッドにおふとんを 1 枚増やすには，そのとき押入れの一番上にあるおふとんをベッドの一番上に乗せるしかない．
逆に，ベッドのおふとんを 1 枚減らすには，そのときベッドの一番上にあるおふとんを押入れの一番上に置くしかない．
また，1 日に動かせるおふとんの枚数に制限は無いが，一度に 1 枚ずつしか動かすことができない．

さて，あなたはこれから買ってきたおふとんを押入れにしまう予定である．
このときに限り，おふとんを好きな順序で押入れにしまうことができる．
どのようにおふとんを押入れに収納し，その後，日々どのようにおふとんを出し入れすれば，快適に毎日を過ごせるだろうか．
M 日間の不快度の和を最小化するとき，その和の値を求めよ．
なお，一度も使われないおふとんがあってもよく，おふとんを一枚も使わない日があってもよい．

Input

入力は複数のデータセットからなる．
各データセットは以下の形式である．

N M
s1 s2 ... sN
d1 d2 ... dM

データセットの 1 行目には，おふとんの枚数 N と，気温が予測されている日数 M を表す整数がスペース区切りで与えられる．
2 行目には N 個の整数 s1, s2, ..., sN がスペース区切りで与えられ，si は i 番のおふとんのぬくもり供給力を表す．
3 行目には M 個の整数 d1, d2, ..., dM がスペース区切りで与えられ，dj は j 日目のぬくもり需要を表す．
これらの整数は，1 ≤ N ≤ 15, 1≤ M ≤ 100, 1 ≤ si, dj ≤ 1,000,000 を満たす．

入力の終わりは N = M = 0 のデータセットで表される．
このデータセットについて出力を行ってはならない．

Output

各データセットについて，M 日間の不快度の和の最小値を 1 行に出力せよ．

Sample Input

1 1
5
6
1 1
5
2
1 1
20
5
4 1
2 4 5 9
8
4 3
3 5 2 1
10 4 7
5 5
2 2 2 2 2
1 3 5 7 9
2 5
2 5
2 5 2 5 2
0 0

Output for Sample Input

1
2
5
1
1
5
4

5 つ目のケースについては，上から 5, 2, 3, 1 と押入れに置き，1 日目は 3 枚取り出し |10 - (5 + 2 + 3)| = 0，2 日目は 2 枚しまい |4 - 5| = 1，3 日目は 1 枚取り出し |7 - (5+2)| = 0 で，合計 0 + 1 + 0 = 1 となる．



Sample input:
1 1
5
6
1 1
5
2
1 1
20
5
4 1
2 4 5 9
8
4 3
3 5 2 1
10 4 7
5 5
2 2 2 2 2
1 3 5 7 9
2 5
2 5
2 5 2 5 2
0 0


Sample output:
1
2
5
1
1
5
4

Submission status: Time Limit Exceeded

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

while True:
    n,m=map(int,input().split())
    if n==m==0:
        break
    s=list(map(int,input().split()))
    d=[0]+list(sorted(map(int,input().split())))
    dp=[[9999999999 if i>0 else 0 for j in range(2**n)] for i in range(m+1)]
    for i in range(m):
        dp[i+1][0]=dp[i][0]+d[i+1]
        for j in range(2**n):
            tmp=0
            for k in range(n):
                if 1<<k & j:
                    tmp+=s[k]
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+abs(d[i+1]-tmp))
            for k in range(n):
                if not (1<<k & j):
                    dp[i+1][j|1<<k]=min(dp[i][j]+abs(d[i+1]-(tmp+s[k])),dp[i+1][j|1<<k])
    print(min(dp[m]))

Submission status: Accepted

Solution code:
from collections import deque
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    D = sorted(map(int, input().split()))

    SA = sum(S)
    rest = sum(d-SA for d in D if SA <= d)

    memo = {2**n-1: rest}
    def dfs(state, su, idx):
        if state in memo:
            return memo[state]
        res = 10**18
        for i in range(n):
            if (state >> i) & 1 == 0:
                s = 0; j = idx
                nxt = su + S[i]
                while j < m and D[j] <= nxt:
                    s += min(nxt - D[j], D[j] - su); j += 1
                res = min(res, s + dfs(state | (1 << i), su + S[i], j))
        memo[state] = res
        return res
    print(dfs(0, 0, 0))

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:break
    ofuton = list(map(int, input().split()))
    dlst = sorted(map(int, input().split()))
    
    INF = 10 ** 20
    end = 2 ** n - 1
    dic = {}
    def min_score(stat, power, index):
      if stat in dic:return dic[stat]
      if stat == end:return 0
      
      mask = 1
      ret = INF
      for i in range(n):
        if mask & stat:
          mask <<= 1
          continue
        new_power = power + ofuton[i]
        new_stat = stat | mask
        new_index = br(dlst, new_power) - 1
        add = (m - new_index - 1) * ofuton[i]
        for j in range(index + 1, new_index + 1):
          if new_power - dlst[j] < dlst[j] - power:
            add += (dlst[j] - power) - (new_power - dlst[j])
        ret = min(ret, -add + min_score(new_stat, new_power, new_index))
        mask <<= 1
      dic[stat] = ret
      return ret
    
    print(sum(dlst) + min_score(0, 0, -1))

main()

Submission status: Runtime Error

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    *D, = map(int, input().split())

    from itertools import permutations
    ans = 10**18
    for P in permutations(S):
        Q = [0]*(n+1)
        for i, e in enumerate(P):
            Q[i+1] = P[i] + Q[i]
        ans = min(ans, sum(min(abs(d - q) for q in Q) for d in D))
    print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    *D, = map(int, input().split())

    def solve(S, D):
        for P in permutations(S):
            Q = [0]*(n+1)
            for i, e in enumerate(P):
                Q[i+1] = P[i] + Q[i]
            yield sum(min(abs(d - q) for q in Q) for d in D)
    print(min(solve(S, D)))

Submission status: Runtime Error

Solution code:
from itertools import permutations
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    *D, = map(int, input().split())

    def solve(S, D):
        Q = [0]*(n+1)
        for P in permutations(S):
            for i, e in enumerate(P):
                Q[i+1] = e + Q[i]
            yield sum(min(abs(d - q) for q in Q) for d in D)
    print(min(solve(S, D)))

Submission status: Runtime Error

Solution code:
from collections import deque
while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    *S, = map(int, input().split())
    *D, = map(int, input().split())

    deq = deque(S)
    D.sort()
    def dfs(r, idx, prev):
        if idx == m:
            return 0
        if r == n:
            s = 0
            while idx < m:
                s += D[idx] - prev
                idx += 1
            return s
        res = 10**18
        for i in range(n - r):
            v = deq.popleft()
            nxt = prev + v
            s = 0; j = idx
            while j < m and D[j] <= nxt:
                s += min(nxt - D[j], D[j] - prev); j += 1
            res = min(res, s + dfs(r+1, j, nxt))
            deq.append(v)
        return res
    print(dfs(0, 0, 0))