Problem p02901 (python)

Fixed submission:
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    cd = {}
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for _ in range(M):
        ai, _ = map(int, input().split())
        ci = sum(1 << (int(i) - 1) for i in input().split())
        keys = list(cd.keys())
        for i in keys:
            cd[i | ci] = min(cd.get(i | ci, FAIL), cd[i] + ai)
        cd[ci] = min(cd.get(ci, FAIL), ai)
    print(cd.get((1 << N) - 1, -1))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from functools import lru_cache

def to_bit(s):
    r = 0
    for i in s:
        r |= 1 << (i - 1)
    return r

def main():
    N, M = map(int, input().split())
    a, c = [], []
    cd = {}
    ALL = (1 << N) - 1
    tall = 0
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = to_bit(map(int, input().split()))
        c.append(cc)
        tall |= cc
        cd[cc] = min(cd.get(cc, FAIL), t)

    if tall != ALL:
        print(-1)
        return

    @lru_cache(maxsize=None)
    def helper(i, opened):
        if opened == ALL:
            return 0
        if i == M:
            return FAIL
        while opened | c[i] == opened:
            i += 1
            if i == M:
                return FAIL
        return min(a[i] + helper(i + 1, opened | c[i]),
                   helper(i + 1, opened))

    print(helper(0, 0))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(2000)
    N, M = map(int, input().split())
    a, c = [], []
    tall = set(range(1, N + 1))
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = frozenset(map(int, input().split()))
        c.append(cc)
        tall = tall - cc
    if tall:
        print(-1)
        return
    FAIL = sum(a) + 1

    @lru_cache(maxsize=None)
    def helper(i, left):
        if not left:
            return 0
        if i == M:
            return FAIL
        return min(a[i] + helper(i + 1, left - c[i]),
                   helper(i + 1, left))

    print(helper(0, frozenset(range(1, N + 1))))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(2000)
    N, M = map(int, input().split())
    a, c = [], []
    tall = set(range(1, N + 1))
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = frozenset(map(int, input().split()))
        c.append(cc)
        tall = tall - cc
    if tall:
        print(-1)
        return
    FAIL = sum(a) + 1

    @lru_cache(maxsize=None)
    def helper(i, price, left):
        if not left:
            return price
        if i == M:
            return FAIL
        return min(helper(i + 1, price + a[i], left - c[i]),
                   helper(i + 1, price, left))

    print(helper(0, 0, frozenset(range(1, N + 1))))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    a, c = [], []
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = set(map(int, input().split()))
        c.append(cc)

    al = set(range(1, N + 1))
    print(helper(0, N, M, a, c, 0, al))

def helper(i, N, M, a, c, price, al):
    if not al:
        return price
    if i == M:
        return -1
    t = helper(i + 1, N, M, a, c, price + a[i], al - c[i])
    s = helper(i + 1, N, M, a, c, price, al)
    if t != -1 and s != -1:
        return min(t, s)
    else:
        return max(t, s)


if __name__ == '__main__':
    main()