Problem p02901 (python)

Fixed submission:
n, m = map(int, input().split())
r = [2**i for i in range(n+1)]

price = [0] * m
mask = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    for box in map(int, input().split()):
        mask[i] += r[box-1]
    price[i] = a


inf = 10**9
dp = [[inf] * (1 << n) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for j in range(1 << n):
        dp[i+1][j | mask[i]] = min(
            dp[i][j] + price[i],
            dp[i+1][j | mask[i]]
        )
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = dp[m][(1 << n) - 1]
if ans == inf:
    print(-1)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    if box_price[i][0] == -1:
        print(-1)
        exit()
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b]:
                ks[kbx[b]] -= 1
                ks[key] += 1
                kbx1[b] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b]:
                ks[kbx[b]] -= 1
                ks[key] += 1
                kbx1[b] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)