Problem:


Score : 500 points

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

All values in input are integers.

1 \leq N \leq 12

1 \leq M \leq 10^3

1 \leq a_i \leq 10^5

1 \leq b_i \leq N

1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

Output

Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
import itertools

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N),zip(AB,C)):
    m = n|c
    dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

# N = int(input())
# A = list(map(int, input().split()))
N, M = map(int, input().split())

# match = [[False] * N for _ in range(M)]
dest = []
cost = [0] * M


for i in range(M):
    cost[i] = int(input().split()[0])
    dest.append(set(map(int, input().split())))

state = defaultdict(lambda: float('inf'))
state[()] = 0

for i in range(N):
    keys = list(state.keys())
    for key in keys:
        for j in range(M):
            next = tuple(set(key) | dest[j])
            state[next] = min(state[next], state[key]+cost[j])

ans = state[tuple(range(1, N+1))]

print(ans if ans < float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = n|c
        dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A, B, C):
    d = defaultdict(lambda : sys.maxsize)
    # @lru_cache(maxsize=None)
    def f(t, v):
        if v >= d[t]:
            return sys.maxsize
        else:
            d[t] = v
        n = None
        for i in range(N):
            if  (1 << i) & t == 0:
                n = i + 1
                break
        else:
            return v

        ret = sys.maxsize
        for i, c in enumerate(C):
            if n in c:
                t_  = t
                for j in c:
                    t_ |= 1 << (j-1)
                ret = min(ret, f(t_, v + A[i]))
        return ret
    ans = f(0, 0)
    return  ans if ans != sys.maxsize else -1


def main():
    N, M = read_int_n()
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = read_int_n()
        A.append(a)
        B.append(b)
        C.append(set(read_int_n()))

    print(slv(N, M, A, B, C))

    # N = 12
    # M = 10**3
    # A = [random.randint(1, 10**5) for _ in range(M)]
    # B = [random.randint(1, N) for _ in range(M)]
    # C = [set([random.randint(1, N)]) for _ in range(M)]
    # print(slv(N, M, A, B, C))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
abc = []

for i in range(M):
  t = list(map(int, input().split()))
  k = list(map(int, input().split()))
  x = 0
  for j in k:
    x += (1 << (j - 1))
  abc.append(t + [x])

def nasu(n):
  ans = inf
  for i in range(1, n - 1):
    if ~n & i == 0:
      ans = min(ans, L[i] + L[n ^ i])
  return ans

inf = 10 ** 10
L = [inf] * (1 << N)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      if ~abc[j][2] & n == 0:
        L[n] = min(L[n], abc[j][0])
    L[n] = min(L[n], nasu(n))
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

if L[-1] == inf:
  print(-1)
else:
  print(L[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:

        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        if i != 0 and data[aaa][2][-1] == ind + 1:
            continue

        for ele in data[aaa][2]:
            now_data[ele - 1] += 1
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()



    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]

    data.sort(key=lambda x: x[0])

    kagi_data = defaultdict(list)
    for i in range(kagi_num):
        a = data[i]
        for ele in a[2]:
            kagi_data[ele].append(i)



    for i in range(1, box_num + 1):
        kagi_data[i] = list(kagi_data[i])
        kagi_data[i].sort()

    if len(kari) != box_num:
        print(-1)
        sys.exit()


    now_data = [0 for i in range(box_num)]
    check(box_num, kagi_num, kagi_data, 0, now_data, 0, data)

    global ans
    print(ans)




# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()

Submission status: Time Limit Exceeded

Solution code:
boxes_n, keys_n = map(int,input().split())

dt = {}
for i in range(keys_n):
	cost, unlock = map(int, input().split())
	dt[(i, cost)] = list(map(int, input().split()))

items = list(dt.keys())
def find_min_cost(items, opened, added):
	if len(opened) == boxes_n:
		return 0
	elif len(items) == 0:
		return 100000000
	min_so_far = find_min_cost(items[1:],opened,added)
	o = opened.copy()
	for i in dt[items[0]]:
		o.add(i)
	added.append(items[0][0])
	other_min = items[0][1] + find_min_cost(items[1:], o,added)
	return min(min_so_far, other_min)

cost = find_min_cost(items, set(),[])
if cost >= 100000000:
	print(-1)
else:
	print(cost)

Submission status: Time Limit Exceeded

Solution code:

def main():
    def solve(box, used, not_used):
        if len(box) == 0:
            return 0
        c = 10e10
        for k in not_used:
            ks = {k}
            m = solve(box - C[k], used or ks, not_used - ks)
            c = min(A[k]+m, c)
        return c

    N, M = map(int, input().split())
    A, B, C = [None]*(M+1), [None]*(M+1), [None]*(M+1)
    Z = set()
    for i in range(M):
        A[i+1], B[i+1] = map(int, input().split())
        C[i+1] = set([int(x) for x in input().split()])
        Z.update(C[i+1])
    if len(Z) < N:
        return -1

    c = solve(set(range(1,N+1)), set(), set(range(1,M+1)))
    if c >= 10e10:
        return -1
    return c

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
from itertools import chain, combinations
from functools import reduce
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
n,m=map(int,input().split())
zz = []
for _ in range(m):
    a,b=map(int,input().split())
    zz.append((a,b,set(map(int,input().split()))))
result=-1
for z in powerset(zz):
    if len(reduce((lambda s,t: s.union(t)), (zzz[2] for zzz in z), set()))==n:
        if result<0:
            result=sum(zzz[0] for zzz in z)
        else:
            result=min(result,sum(zzz[0] for zzz in z))
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    ci = list(map(int, input().split()))
    c.append(ci)


flag = False
ans = 100000000000000

for i in range(1 << m):
    ls = []
    money = 0
    for j in range(m):
        if(1 << j & i):
            money += a[j]
            for ci in c[j]:
                ls.append(ci)
            ls = list(set(ls))
    if(len(ls) == n):
        ans = min(ans, money)
        flag = True

if(flag):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(lambda x:int(x)-1,input().split()))
key=[[] for _ in range(n)]
for i in range(m):
    for j in c[i]:
        key[j].append(i)

ans=float('inf')
def serch(keyset,i,box):
    global ans
    if i==n:
        if box==set(range(n)):
            ans=min(ans,sum(a[k] for k in keyset))
    else:
        if i in box:
            serch(keyset,i+1,box)
        else:
            for k in key[i]:
                serch(keyset|{k},i+1,box|set(c[k]))

serch(set([]),0,set([]))
print(-1 if ans==float('inf') else ans)

Submission status: Time Limit Exceeded

Solution code:
def to_bit(n):
	ret = [0 for i in range(12)]
	i = 0
	while n > 1:
		ret[i] = n % 2
		n = n // 2
	return ret

def to_int(B):
	return sum([B[i] * 2**i for i in range(12)])

N,M = map(int,input().split())
key = []
for i in range(M):
	a,b = map(int,input().split())
	c = list(map(int,input().split()))
	C = [0 for x in range(12)]
	for x in c:
		C[x-1] = 1
	key.append((a, to_int(C)))
dp = [[-1 if j > 0 else 0 for j in range(2**N)] for i in range(M)]
dp[0][key[0][1]] = key[0][0]
for i in range(M-1):
	cost = key[i+1][0]
	bit = key[i+1][1]
	for j in range(2**N):
		if dp[i][j] >= 0:
			if dp[i+1][j] == -1:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = min(dp[i+1][j], dp[i][j])
			I = i+1
			J = j | bit
			if dp[I][J] == -1:
				dp[I][J] = dp[i][j] + cost
			else:
				dp[I][J] = min(dp[I][J], dp[i][j] + cost)
print(dp[M-1][2**N-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N, M = map(int, input().split())
    dp = np.array([-1]*2**N, dtype=np.uint32)
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        d = sum(2**(c-1) for c in  map(int, input().split()))
        for j,e in enumerate(dp):
            if d|j == d:
                dp[j] = min(e,a)
            else:
                k = j-(j&d)
                dp[j] = min(e, dp[k]+a)

    res = dp[-1] if dp[-1] < np.uint32(-1) else -1
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = now_data_kari.copy()

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:

        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = now_data_kari.copy()
        for ele in data[aaa][1]:
            now_data[ele - 1] += 1
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()

    kagi_data = defaultdict(set)

    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a, b]
        for ele in b:
            kagi_data[ele].add(i)

    for i in range(1, box_num + 1):
        kagi_data[i] = list(kagi_data[i])
        kagi_data[i].sort()

    if len(kari) != box_num:
        print(-1)
        sys.exit()

    # print(data)
    # print(kagi_data)

    now_data = [0 for i in range(box_num)]
    check(box_num, kagi_num, kagi_data, 0, now_data, 0, data)

    global ans
    print(ans)




# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()

Submission status: Time Limit Exceeded

Solution code:
def flatten(nested_list):
    """2重のリストをフラットにする関数"""
    return [e for inner_list in nested_list for e in inner_list]
money = 1000000000000000
n, m = map(int, input().split())
result = list(range(1, n+1))
data = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    data.append([a, c])
n = len(data)
for i in range(2 ** n):
    cbag = []
    bag = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag += data[j][0]  # フラグが立っていたら bag に果
            cbag.append(data[j][1])
    #print("aaa")
    b = list(set(flatten(cbag)))
    #print(b)
    #print(bag)
    if b==result:
        if(money > bag):money=bag
if(money==1000000000000000):print(-1)
else:print(money)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  la=[]
  lc=[]
  for _ in range(m):
    _a,_b=LI()
    la.append(_a)
    _c=LI()
    lc.append(_c)

  l=[]
  a=len(bin(1<<m))-3
  for i in range(1<<m):
    l.append(str(bin(i))[2:].zfill(a))

  ans=inf
  for x in l:
    _ans=0
    _l=[0]*n
    for i,y in enumerate(x):
      if y=='1':
        _ans+=la[i]
        z=lc[i]
        for _z in z:
          _l[_z-1]=1
    if 0 not in _l:
      ans=min(ans,_ans)

  if ans==inf:
    return -1

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(lambda x:int(x)-1,input().split()))
key=[[] for _ in range(n)]
for i in range(m):
    for j in c[i]:
        key[j].append(i)

ans=float('inf')
def serch(keyset,i):
    global ans
    if i==n:
        s=set([])
        for k in keyset:
            s|=set(c[k])
        if s==set(range(n)):
            ans=min(ans,sum(a[k] for k in keyset))
    else:
        if any(k in key[i] for k in keyset):
            serch(keyset,i+1)
        else:
            for k in key[i]:
                serch(keyset|{k},i+1)

serch(set([]),0)
print(-1 if ans==float('inf') else ans)

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append([a, c])

ans = float('inf')
for b in range(2**(M)):
    opened = set()
    money = 0
    for key in range(M):
        if (b >> key) & 1:  # key番目の鍵を買う
            money += keys[key][0]
            opened |= keys[key][1]
        if len(opened) == N:
            break
    if len(opened) == N:
        ans = min(ans, money)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
afs = []
for i in range(M):
  a, b = map(int, input().split())
  cs = map(int, input().split())
  f = 0
  for c in cs:
    f = f|(1<<(c-1))
  afs.append((a, f))
dp = [{} for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
  d = dp[i]
  a0, f0 = afs[i]
  d2 = {}
  for f in d:
    d2[f] = d[f]
  for f in d:
    f2 = f|f0
    a2 = d[f]+a0
    d2[f2] = a2 if f2 not in d2 else min(d2[f2], a2)
  dp[i+1] = d2
#print(dp)
if (1<<N)-1 in dp[M]:
  r = dp[M][(1<<N)-1]
else:
  r = -1
print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    from collections import defaultdict
    import itertools
    import copy
    one = [True, False]
    
    N,M = map(int,input().split())
    dp = []
    for i in range(M+1):
        dp.append(defaultdict(lambda : float("inf")))
    dp[0][(False,)*N] = 0
    
    for i in range(1,M+1):
        #print(dp[M][(True,)*N])
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        for j in itertools.product(one, repeat = N):
            now = list(copy.deepcopy(j))
            for k in c:
                now[k-1] = True
            now = tuple(now)
            dp[i][j] = dp[i-1][j]
            dp[i][now] = min(dp[i][now],dp[i-1][now], dp[i-1][j]+a)
    
    if dp[M][(True,)*N] == float("inf"):
        print(-1)
    else:
        print(dp[M][(True,)*N])
            
    
    
main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

costs = [None for i in range(M)]
opens = [None for i in range(M)]

for i in range(M):
    costs[i] = list(map(int,input().split()))[0]
    opens[i] = list(map(int, input().split()))

dp = {}
dp[tuple(0 for i in range(N))] = 0

def recurse(required):
    if required in dp:
        return dp[required]

    totalCost = float('inf')
    for i in range(M):
        c = list(required)
        for item in opens[i]:
            c[item-1] = 0
        if tuple(c) == required:continue
        totalCost = min(totalCost, costs[i] + recurse(tuple(c)))

    dp[required] = totalCost
    return totalCost


val = recurse(tuple(1 for i in range(N)))
if val == float('inf'):
    print(-1)
else:
    print(val)

Submission status: Accepted

Solution code:
INF = 10**9

N, M = map(int, input().split())
key = []
for _ in range(M):
    ab = list(map(int, input().split()))
    box = list(map(int, input().split()))
    index = sum(list(map(lambda x:2**(x-1), box)))
    ab.append(index)
    key.append(ab)
dp = [[key[0][0] if (i & ~key[0][2]) == 0 else INF for i in range(2**N)]]
dp[0][0] = 0
for j in range(1, M):
    next = [0 for _ in range(2**N)]
    for i in range(2**N):
        next[i] = min(dp[j-1][i], dp[j-1][(i & ~key[j][2])]+key[j][0])
    dp.append(next)
if dp[-1][-1] > 10**7:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Accepted

Solution code:
# ABC142 E

f=lambda:map(int,input().split())
N,M=f()
INF=float('inf')

dp=[[INF]*(1<<N) for _ in [0]*(M+1)]
dp[0][0]=0
# dp[m][s]:=n個目まででsを開けるために必要な最小コスト
def list2int(A):
    res=0
    for a in A:
        res+=2**(a-1)
    return res
    
for m in range(M):
    a,b=f()
    c=list2int(list(f()))
    for i in range(1<<N):
        # 次のカギ買った
        dp[m+1][i|c]=min(dp[m][i]+a,dp[m+1][i|c])
        # やめといた
        dp[m+1][i]=min(dp[m][i],dp[m+1][i])
res=dp[M][(1<<N)-1]
print(res if res<INF else -1)

Submission status: Accepted

Solution code:
INF = 10**9

def as_bit(ls):
    # 開けられる宝箱をbitで示す
    ret = 0
    for l in ls:
        ret |= 1 << (l - 1)
    return ret

def main():
    
    N, M = map(int, input().split())
    C, A = [], []
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        c = list(map(int, input().split()))
        C.append(as_bit(c))

    dp = [[INF] * (2**N) for _ in range(M+1)]

    for i in range(M+1):
        dp[i][0] = 0

    for i in range(M):
        for bit in range(2**N):
            dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i])
            dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit])

    ans = dp[-1][-1]
    print(ans if ans != INF else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [-1 for i in range(2**n)]
    dp[0] = 0

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==-1:
                continue
            new = dp[j]
            
            update = int(curk,2)|j
            
            #print(i,j,update,new,curc,curk,s)
            target = temp[update]
            if target==-1:
                temp[update] = new+curc
            elif target>new+curc:
                temp[update] = new+curc                
            if new<temp[j] or temp[j]==-1:
                temp[j] = dp[j]
        dp = temp
        #print(dp)
    print(dp[-1])
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [-1 for i in range(2**n)]
    dp[0] = 0
    
    
    def intersect(bit1,bit2):
        s = ""
        for i in range(n):
            if bit1[i]=="1" or bit2[i]=="1":
                s = "".join([s,"1"])
            else:
                s = "".join([s,"0"])
        return int(s,2)

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==-1:
                continue
            new = dp[j]
            
            s = bin(j)[2:]
            if len(s)!=n:
                while len(s)<n:
                    s = "".join(["0",s])
            update = intersect(curk,s)
            
            #print(i,j,update,new,curc,curk,s)
            target = temp[update]
            if target==-1:
                temp[update] = new+curc
            elif target>new+curc:
                temp[update] = new+curc                
            if new<temp[j] or temp[j]==-1:
                temp[j] = dp[j]
        dp = temp
        #print(dp)
    print(dp[-1])
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M = map(int, input().split())
prices = [0] * M
ks = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    prices[i] = a
    ks[i] = C

dp = [INF] * (1 << N)
dp[0] = 0
for i in range(M):
    key_bit = 0
    for k in ks[i]:
        key_bit |= 1 << (k - 1)
    for bit in range((1 << N) - 1, -1, -1):
        if dp[bit] != INF:
            nx_bit = bit | key_bit
            dp[nx_bit] = min(dp[nx_bit], dp[bit] + prices[i])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
price_value = []
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    v = ["0"]*N
    for i in range(N):
        if i+1 in c:
            v[i] = "1"
    v = "".join(v)
    v = int(v, base=2)
    price_value.append((a, v))

INF = float("inf")
dp = [[INF] * (2**N) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1, M+1):
    price, value = price_value[i-1]
    for j in range(2**N):
        dp[i][j | value] = min(
            dp[i][j | value], dp[i-1][j] + price
        )
        dp[i][j] = min(dp[i][j], dp[i-1][j])
ans = dp[-1][-1]
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
INF = 10 ** 10
dp = [INF] * (2 ** N)
dp[0] = 0

for i in range(M):
  a,b = map(int,readline().split())
  c = list(map(int,readline().split()))
  key = 0
  for j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    if j | key == j:
      continue
    if dp[j | key] > dp[j] + a:
      dp[j | key] = dp[j] + a

if dp[-1] == INF:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
INF = 10 ** 10
dp = [INF] * (2 ** N)
dp[0] = 0

for i in range(M):
  a,b = map(int,readline().split())
  c = list(map(int,readline().split()))
  key = 0
  for j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    if j | key == j:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

if dp[-1] == INF:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C |= (1 << (c - 1))
    Key.append(C)
DP = [float('inf')] * (1 << N)
DP[0] = 0

for cost, key in zip(Cost, Key):
    D = DP[:]
    for i, d in enumerate(DP):
        if d == float('inf'):
            continue
        D[i|key] = min(D[i|key], d + cost)
    DP = D

if DP[-1] == float('inf'):
    print(-1)
else:
    print(DP[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
newcount = [100000000 for _ in range(2**N)]
newcount[0] = 0
bi = [1,2,4,8,16,32,64,128,256,512,1024,2048]
for k in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bit = 0
  for k in range(b):
    bit += bi[c[k]-1]
  count = tuple(newcount)
  for k in range(2**N):
    now = bit|k
    newcount[now] = min(newcount[now], a+count[k])
if newcount[-1] < 10**7:
  print(newcount[-1])
else:
  print(-1)