Problem:


ビートパネル

遊太君は、近所のゲームセンターで人気のゲーム「ビートパネル」にはまっています。このゲームは図のようなグリッド状に並べられた 4×4 の計16個のパネル型のボタンからなります。

図のように、左上から右下にボタン1, ボタン2, …, ボタン16の順にボタンが並んでいます。ゲームでは一定間隔でビート音が鳴り最後に終了音が鳴ります。ビート音が鳴ると同時に複数のボタンが光ります。１個も光らない場合もあります。プレイヤーは、ビート音が鳴った直後から次の音が鳴るまでの間に両手の指を使って複数のボタンを１度だけ同時に押すことができます。何も押さないということも可能です。終了音が鳴ったと同時にゲームは終了します。

遊太君は c 通りの押し方を習得しており、ビート音が鳴る度に、それらの押し方の中から１つ決めてボタンを押します。押したボタンが光っていれば、それらのボタンの光は消え、消えたボタンの数がプレイヤーのスコアに加算されます。また、一度光ったボタンはそのボタンが押されるまで光は消えることはありません。

ビート音が n 回鳴るときのボタンの光り方と遊太君が習得している c 通りのボタンの押し方を入力とし、遊太君が獲得することのできる得点の最大値を出力するプログラムを作成してください。

入力

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

n c
a1,1 a1,2 ... a1,16
a2,1 a2,2 ... a2,16
...
an,1 an,2 ... an,16
b1,1 b1,2 ... b1,16
b2,1 b2,2 ... b2,16
...
bc,1 bc,2 ... bc,16

１行目は１つの空白で区切られた２つの整数からなる。n (1 ≤ n ≤ 30) はビート音の数、c (1 ≤ c ≤ 30) は習得しているボタンの押し方の数を示す。続く n＋c 行にボタンの光り方とボタンの押し方が与えられる。行中の入力項目の区切りは１つの空白である。ak,i は k 回目のビート音が鳴ったときのボタン i の光り方を、bj,i は c 通り中 j 番目の押し方でボタン i が押されるかどうかを表す。ak,iの値は 0 が「光らない」、1 が「光る」を表す。bj,i の値は 0 が「押さない」、1 が「押す」を表す。

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

出力

各データセットごとに、得点の最大値を１行に出力する。

入力例

2 2
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
2 2
0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0
0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
5 3
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0

出力例

8
7
16



Sample input:
2 2
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
2 2
0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0
0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
5 3
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0


Sample output:
8
7
16

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b):
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            for bi in b:
                vb = v + st(k, bi)
                kb = k & (65535 ^ bi) | ai
                try:
                    ndp[kb] = max(ndp[kb], vb)
                except KeyError:
                    ndp[kb] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

def st(i, j):
    return bin(i).count('1') - bin(i & (65535 ^ j)).count('1')

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b):
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            for bi in b:
                vb = v + st(k, bi)
                kb = k & (65535 ^ bi) | ai
                try:
                    ndp[kb] = max(ndp[kb], vb)
                except KeyError:
                    ndp[kb] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memoize
def st(i, j):
    return bin(i).count('1') - bin(i & (65535 ^ j)).count('1')



import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b):
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bin(k).count('1')
            for bi in b:
                bi &= k
                vb = v - bin(bi).count('1')
                bi |= ai
                try:
                    ndp[bi] = max(ndp[bi], vb)
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(0x10000)]

def solve(a, b):
    global bitcount
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bitcount[k]
            for bi in b:
                bi &= k
                vb = v - bitcount[bi]
                bi |= ai
                try:
                    ndp[bi] = max(ndp[bi], vb)
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    ass = [[int(s) for s in input().split()] for _ in range(n)]
    bss = [[int(s) for s in input().split()] for _ in range(c)]
    

    ps = {(0,)*16 : 0}
    for as_ in ass:
        qs = ((tuple(a|b for a,b in zip(p,as_)),x) for p,x in ps.items())
        ps = {}
        for q,x in qs:
            for bs in bss:
                p = tuple(a&~b for a,b in zip(q,bs))
                y = x + sum(q) - sum(p)
                if p not in ps or ps[p] < y:
                    ps[p] = y
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    ps = {0 : 0}
    for a in as_:
        qs = ((p|a,x) for p,x in ps.items())
        ps = {}
        for q,x in qs:
            for b in bs:
                p = q&~b
                y = x + bin(q).count('1') - bin(p).count('1')
                if p not in ps or ps[p] < y:
                    ps[p] = y
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(1<<16)]

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    ps = {0 : 0}
    for a in as_:
        qs = ((x|a,n) for x,n in ps.items())
        ps = {}
        for x,n in qs:
            for b in bs:
                m = n+bitcount[x&b]
                y = x&~b
                if y not in ps or ps[y] < m:
                    ps[y] = m
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(1<<16)]

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    ps = {0 : 0}
    for a in as_:
        qs = ((x|a,n) for x,n in ps.items())
        ps = {}
        for x,n in qs:
            for b in bs:
                y = x&~b
                m = n+bitcount[x&b]
                try:
                    if ps[y] < m:
                        ps[y] = m
                except KeyError:
                    ps[y] = m
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(1<<16)]

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    ps = {0 : 0}
    qs = {}
    for a in as_:
        for x,n in ps.items():
            x |= a
            for b in bs:
                y = x&~b
                m = n+bitcount[x&b]
                try:
                    if qs[y] < m:
                        qs[y] = m
                except KeyError:
                    qs[y] = m
        ps,qs = qs,{}
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(1<<16)]

def f(as_,bs):
    global bitcount
    ps = {0 : 0}
    qs = {}
    for a in as_:
        for x,n in ps.items():
            x |= a
            for b in bs:
                y = x&~b
                m = n+bitcount[x&b]
                try:
                    if qs[y] < m:
                        qs[y] = m
                except KeyError:
                    qs[y] = m
        ps,qs = qs,{}
    return max(ps.values())

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    print(f(as_,bs))

Submission status: Time Limit Exceeded

Solution code:
bitcount = [bin(i).count('1') for i in range(1<<16)]

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    ps = {as_[0] : 0}
    qs = {}
    for a in as_:
        for x,n in ps.items():
            x |= a
            for b in bs:
                y = x&~b
                m = n+bitcount[x&b]
                if y not in qs or qs[y] < m:
                    qs[y] = m
        ps,qs = qs,{}
    print(max(ps.values()))

Submission status: Time Limit Exceeded

Solution code:
arr = [-1]*(1<<16)

while True:
    n,c = map(int,input().split())
    if n == c == 0:
        break
    as_ = [int(input().replace(' ',''),2) for _ in range(n)]
    bs = [int(input().replace(' ',''),2) for _ in range(c)]
    
    arr[0] = 0
    for a in as_:
        ps = [(x,n) for x,n in enumerate(arr) if n!=-1]
        for x,_ in ps:
            arr[x] = -1
        for x,n in ((x|a,n) for x,n in ps):
            for b in bs:
                y = x&~b
                m = n+bin(x&b).count('1')
                if arr[y]==-1 or arr[y]<m:
                    arr[y]=m
    print(max(arr))
    arr.clear()
    arr.extend(-1 for _ in range(1<<16))

Submission status: Accepted

Solution code:
bitcount = [bin(i).count('1') for i in range(0x10000)]
def solve(a, b):
    global bitcount
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bitcount[k]
            for bi in b:
                bi &= k
                vb = v - bitcount[bi]
                bi |= ai
                try:
                    if ndp[bi] < vb:
                        ndp[bi] = vb
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin


while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

Submission status: Accepted

Solution code:
# using DP
# time complexity: O(n * (2^16) * c)
# 1 <= n <= 30, 1 <= c <= 30
# worst case: 30 * (2^16) * 30 = 58982400

bc = [bin(i).count('1') for i in range(65536)] # bitcount

def solve():
    from sys import stdin
    f_i = stdin
    
    while True:
        n, c = map(int, f_i.readline().split())
        if n == 0:
            break
        
        A = [int(f_i.readline().replace(' ', ''), 2) for i in range(n)]
        B = [int(f_i.readline().replace(' ', ''), 2) for i in range(c)]
        
        dp1 = {A[0]: 0} # {state: score}
        dp2 = {}
        
        for a in A[1:] + [0]:
            for st1, sc1 in dp1.items():
                for b in B:
                    cb = st1 & b
                    sc2 = sc1 + bc[cb]
                    st2 = (st1 - cb) | a
                    try:
                        if dp2[st2] < sc2:
                            dp2[st2] = sc2
                    except KeyError:
                        dp2[st2] = sc2
            dp1, dp2 = dp2, {}
        
        print(max(dp1.values()))

solve()

Submission status: Accepted

Solution code:
def main():
  while True:
    n, c = map(int, input().split())
    if n == 0:break
    music = []
    for _ in range(n):
      line = list(map(int, input().split()))
      add_panel = sum([2 ** i * line[i] for i in range(16)])
      music.append(add_panel)
    
    hand = []
    for _ in range(c):
      line = list(map(int, input().split()))
      erase_panel = sum([2 ** i * line[i] for i in range(16)])
      hand.append(erase_panel)

    masks = tuple([2 ** i for i in range(16)])
    move = [{} for _ in range(2 ** 16)]
    
    dp = [{} for _ in range(n + 1)]
    dp[0][0] = 0
    for turn in range(n):
      add_panel = music[turn]
      dp_next_turn = dp[turn + 1]
      used = {}
      for state, score in sorted(dp[turn].items(), key=lambda x:-x[1]):
        new_state = add_panel | state
        if new_state in used:continue
        used[new_state] = True
        move_new_state = move[new_state]
        for erase_panel in hand:
          if erase_panel in move_new_state:
            erased_state, add_score = move_new_state[erase_panel]
          else:
            add_score = 0
            temp = erase_panel & new_state
            for mask in masks:
              if mask > temp:break
              if temp & mask:
                add_score += 1
            erased_state = new_state & ~erase_panel
            move_new_state[erase_panel] = (erased_state, add_score)
          
          new_score = score + add_score
          if erased_state not in dp_next_turn or dp_next_turn[erased_state] < new_score:
            dp_next_turn[erased_state] = new_score
    
    print(max(dp[n].values()))

main()

Submission status: Runtime Error

Solution code:
def solve(a, b):
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            for bi in b:
                vb = v + st(k, bi)
                kb = k & (65535 ^ bi) | ai
                try:
                    ndp[kb] = max(ndp[kb], vb)
                except KeyError:
                    ndp[kb] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

@memoize
def st(i, j):
    return bin(i).count('1') - bin(i & (65535 ^ j)).count('1')

def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))