Problem:


微生物発電

飯沼博士は磐梯山の噴気孔でふしぎな微生物を見つけました。この微生物の雄と雌１体ずつが合体すると、電気エネルギーを放出します。この微生物を研究すれば、将来のエネルギー危機から我々を救えるかもしれません。

観察を続けると、微生物は合体したときだけ電気エネルギーを発生させることと、合体した微生物のさらなる合体はないことがわかりました。さらに観察を続けると、合体で放出される電気エネルギーは、微生物が体内に持つ未知の粒子（博士はこれを磐梯山にちなんでＢ粒子と名づけました）の量で決まることがわかりました。合体する雄と雌が体内に持つＢ粒子の量をそれぞれ bm と bw とすると、合体により放出される電気エネルギーは |bm - bw| &times; (|bm - bw| - 30)2 という式で計算できます。

この発見により、微生物の集団から得られる最大の電気エネルギーが計算できるようになりました。それでは、微生物の集団に含まれる雄と雌の数と、各個体が持つＢ粒子の量が与えられたとき、この微生物の集団から得られる最大の電気エネルギーを計算するプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ2つの行で示される。入力データは以下の形式で与えられる。

M W
bm1 bm2 ... bmM
bw1 bw2 ... bwW

１行目の M と W (1 ≤ M,W ≤ 12) はそれぞれ雄と雌の微生物の数である。２行目に、i 番目の雄が体内に持つＢ粒子の量 bmi (0 ≤ bmi ≤ 50) が与えられる。３行目に、i 番目の雌が体内に持つＢ粒子の量 bwi (0 ≤ bwi ≤ 50) が与えられる。

データセットの数は 20 を超えない。

出力

データセットごとに、微生物の集団から得られる電気エネルギーの最大値を1行に出力する。

入出力例

入力例

3 3
0 20 30
10 20 30
10 10
32 10 15 8 20 10 6 45 50 41
18 0 37 25 45 11 25 21 32 27
7 3
23 14 39 6 47 16 23
19 37 8
0 0

出力例

12000
53906
11629



Sample input:
3 3
0 20 30
10 20 30
10 10
32 10 15 8 20 10 6 45 50 41
18 0 37 25 45 11 25 21 32 27
7 3
23 14 39 6 47 16 23
19 37 8
0 0


Sample output:
12000
53906
11629

Submission status: Wrong Answer

Solution code:
def get_energy(bm, bw):
    tmp = abs(bm-bw)
    return tmp * ((tmp-30) ** 2)

def calc(bsa, bla):
    value = 0

    if not bsa:
        return 0

    bs = bsa.pop()
    sz = len(bla)
    for i in range(sz):
        bl = bla.pop(i)
        tmp = get_energy(bl, bs) + calc(bsa, bla)
        if tmp > value:
            value = tmp
        bla.insert(i, bl)
    bsa.append(bs)
    return value

s = map(int, raw_input().split())
M = s[0]
W = s[1]
if M <= W:
    bsa = map(int, raw_input().split())
    bla = map(int, raw_input().split())
else:
    bla = map(int, raw_input().split())
    bsa = map(int, raw_input().split())

print "%d" % calc(bsa, bla)

Submission status: Time Limit Exceeded

Solution code:
def get_energy(bm, bw):
    tmp = abs(bm-bw)
    return tmp * ((tmp-30) ** 2)

def calc(bsa, bla):
    value = 0

    if not bsa:
        return 0

    bs = bsa.pop()
    sz = len(bla)
    for i in range(sz):
        bl = bla.pop(i)
        tmp = get_energy(bl, bs) + calc(bsa, bla)
        if tmp > value:
            value = tmp
        bla.insert(i, bl)
    bsa.append(bs)
    return value

while True:
    s = map(int, raw_input().split())
    M = s[0]
    W = s[1]
    if M == 0 and W == 0:
        break
    if M <= W:
        bsa = map(int, raw_input().split())
        bla = map(int, raw_input().split())
    else:
        bla = map(int, raw_input().split())
        bsa = map(int, raw_input().split())

    print "%d" % calc(bsa, bla)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

while 1:
    M, W = map(int, input().split())
    if M == W == 0:
        break
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    mcf = MinCostFlow(M+W+2)
    for i in range(M):
        mcf.add_edge(0, i+1, 1, 0)
    for i in range(M):
        for j in range(W):
            d = abs(A[i] - B[j])
            mcf.add_edge(i+1, M+1+j, 1, -d*(d-30)*(d-30))
    for i in range(W):
        mcf.add_edge(M+1+i, M+W+1, 1, 0)
    print(-mcf.flow(0, M+W+1, min(M, W)))

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
#MOD = 1000000007
MOD = 10000
EPS = 0.000000001
sys.setrecursionlimit(100000)


SIZE = 13
POW = [1] * (SIZE)
for i in range(1,SIZE):
    POW[i] = POW[i-1]*2

while True:
    M,W = map(int,input().split())
    if M == 0 and W == 0:
        break

    table = []

    table.append(list(map(int,input().split()))) #Mの読み込み
    table.append(list(map(int,input().split()))) #Wの読み込み

    small = None
    large = None
    if M < W:
        small = 0
        large = 1
    else:
        small = 1
        large = 0

    len_small = len(table[small])
    len_large = len(table[large])

    dp = [[-BIG_NUM]*POW[len_large] for _ in range(len_small+1)] #要素数が大きい方を常態化する(少ない方は全部使うため)

    ans = 0
    dp[0][0] = 0 #dp[少ない方のインデックス(1開始)][多い方の使用状態] = 最大値

    for i in range(len_small): #今回マッチさせる微生物のループ(少ない側)
        for state in range(0,POW[len_large]): #既に使った微生物のループ(大きい側)
            if dp[i][state] == -BIG_NUM:
                continue
            for k in range(len_large):
                if state & POW[k] != 0:
                    continue
                next_state = state+POW[k]
                next_value = dp[i][state]+abs(table[small][i]-table[large][k])* \
                    (abs(table[small][i]-table[large][k])-30)*(abs(table[small][i]-table[large][k])-30)

                dp[i+1][next_state] = max(dp[i+1][next_state],next_value)
                ans = max(ans,next_value)

    print("%d"%(ans))

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    def f(bm_i, bw_i):
        if bm_i > bw_i:
            d = bm_i - bw_i
        else:
            d = bw_i - bm_i
        return d * (d - 30) ** 2
    
    while True:
        M, W = map(int, f_i.readline().split())
        if M == 0:
            break
        
        bm = list(map(int, f_i.readline().split()))
        bw = list(map(int, f_i.readline().split()))
        
        e_gen = [[f(m, w) for w in bw] for m in bm]
        
        bit_size = (1 << W)
        dp1 = [-1] * bit_size
        dp2 = [-1] * bit_size
        dp1[0] = 0
        dp2[0] = 0
        add_bit = [1 << i for i in range(W)]
        
        for i in range(M):
            for s1, e1 in enumerate(dp1):
                if e1 == -1:
                    continue
                for b, e in zip(add_bit, e_gen[i]):
                    if s1 & b:
                        continue
                    s2 = s1 | b
                    e2 = e1 + e
                    if e2 > dp2[s2]:
                        dp2[s2] = e2
            dp1 = dp2[:]
        print(max(dp2))

solve()

Submission status: Accepted

Solution code:
import itertools as ite
import math

INF = 10 ** 18

while True:
    M, W = map(int, raw_input().split())
    if M == 0:
        break
    bm = map(int, raw_input().split())
    bw = map(int, raw_input().split())
    if M < W:
        M, W = W, M
        bm, bw = bw, bm
    DP = [0] * (1 << M)
    for i in range(1 << M):
        cnt = 0
        for j in range(M):
            if i & (1 << j):
                cnt += 1
        if cnt > W:
            continue
        for j in range(M):
            if i & (1 << j):
                num = abs(bw[cnt - 1] - bm[j]) * (abs(bw[cnt - 1] - bm[j]) - 30) ** 2
                DP[i] = max(DP[i], DP[i - (1 << j)] + num)
    print max(DP)

Submission status: Accepted

Solution code:
def main():
  while True:
    m, w = map(int, input().split())
    if m == 0:
      break
  
    if m >= w:
      long_lst = list(map(int, input().split()))
      short_lst = list(map(int, input().split()))
      rest = 2 ** m - 1
    else:
      short_lst = list(map(int, input().split()))
      long_lst = list(map(int, input().split()))
      rest = 2 ** w - 1
    mem = [None] * (rest + 1)
  
    def elec(bm, bw):
      bd = abs(bm - bw)
      return bd * (bd - 30) ** 2
  
    def score(rest, index):
      if mem[rest] != None:
        return mem[rest]
      if rest == 0 or index < 0:
        return 0
  
      mask = 1
      count = 0
      ret = 0
      while mask <= rest:
        if mask & rest:
          new_rest = rest & ~mask
          ret = max(ret, score(new_rest, index - 1) + elec(short_lst[index], long_lst[count]))
        mask <<= 1
        count += 1
  
      mem[rest] = ret
      return ret
  
    print(score(rest, min(m, w) - 1))
  
main()

Submission status: Runtime Error

Solution code:
def get_energy(bm, bw):
    tmp = abs(bm-bw)
    return tmp * ((tmp-30) ** 2)

def calc(bsa, bla):
    value = 0

    if not bsa:
        return 0

    bs = bsa.pop()
    sz = len(bla)
    for i in range(sz):
        bl = bla.pop(i)
        tmp = get_energy(bl, bs) + calc(bsa, bla)
        if tmp > value:
            value = tmp
        bla.insert(i, bl)
    bsa.append(bs)
    return value

while True:
    s = map(int, raw_input().split())
    M = s[0]
    W = s[1]
    if M == 0 and N == 0:
        break
    if M <= W:
        bsa = map(int, raw_input().split())
        bla = map(int, raw_input().split())
    else:
        bla = map(int, raw_input().split())
        bsa = map(int, raw_input().split())

    print "%d" % calc(bsa, bla)