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:
N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | key[i][0] # 遷移先
    cost = dp[s] + key[i][1]
    dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
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 d in C:
        c+=2**(d-1)
    key.append((a,b,c))

dp=np.ones((2**N))*np.inf
dp[0]=0
for bi in range(0,2**N):
    for i in range(M):
        t=key[i]
        a,b,c=t
        

        dp[bi|c]=min(dp[bi]+a,dp[bi|c])
if dp[-1]!=np.inf:
    print(int(dp[-1]))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j in range(n_bit):
    for i in range(m):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for i in range(m):
    for j in range(n_bit):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*n_bit for _ in range(m+1)]
dp[0][0] = 0

# 配る
for i in range(m):
    for j in range(n_bit):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy as copy
import sys
input = sys.stdin.readline

def main(): 
    N, M = list(map(int, input().split()))
    n = 2**N

    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(M):
        a, b = list(map(int, input().split()))
        t = 0

        for c in list(map(int, input().split())):
            t += 2**(c-1)

        dp_next = copy(dp)

        for j in range(n):
            dp_next[j|t] = min(dp[j|t], dp_next[j|t], dp[j]+a)

        dp = copy(dp_next)
        
    ans = dp[-1]
    
    if ans == float('inf'): print(-1)
    else: print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main(): 
    N, M = list(map(int, input().split()))
    n = 2**N
    dp = [[float('inf') for i in range(n)] for j in range(M+1)]
    for i in range(M+1): dp[i][0] = 0

    for i in range(1, M+1):
        a, b = list(map(int, input().split()))
        t = 0

        for c in list(map(int, input().split())):
            t += 2**(c-1)

        for j in range(n): dp[i][j] = dp[i-1][j]
        for j in range(n):
            dp[i][j | t] = min(dp[i][j | t], dp[i-1][j | t], dp[i-1][j]+a)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
n = 2**N
dp = [[float('inf') for i in range(n)] for j in range(M+1)]
for i in range(M+1): dp[i][0] = 0

for i in range(1, M+1):
    a, b = list(map(int, input().split()))
    t = 0

    for c in list(map(int, input().split())):
        t += 2**(c-1)

    for j in range(n): dp[i][j] = dp[i-1][j]
    for j in range(n):
        dp[i][j | t] = min(dp[i][j | t], dp[i-1][j | t], dp[i-1][j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list += [a]
    c += [sum(1 << j-1 for j in list(map(int,input().split())))]

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for A,C in zip(a_list,c):
        dp[C|i] = min(dp[C|i],dp[i]+A)

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list += [a]
    c += [sum(1 << j-1 for j in list(map(int,input().split())))]

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int,input().split())
a_list = []
li = [[0 for i in range(n)] for j in range(m)]

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c = list(map(int,input().split()))
    for j in range(b):
        c[j] -= 1
    for k in c:
        li[i][k] = 1

li = np.array(li)
min_coin = 10**10
for i in range(2**m):
    coin = 0
    bool_list = np.array([0]*n)
    for j in range(m):
        if (i >> j)&1:
            for k in li[j]:
                bool_list = li[j] | bool_list
            coin += a_list[j]
    if np.count_nonzero(bool_list) != n:
        continue
    min_coin = min(min_coin,coin)

if min_coin == 10**10:
    print(-1)
else:
    print(min_coin)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_list = []
li = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c = list(map(int,input().split()))
    for j in range(b):
        c[j] -= 1
    li.append(c)

min_coin = 10**10

for i in range(2**m):
    bool_list = []
    coin = 0
    for j in range(m):
        if (i >> j)&1:
            for k in li[j]:
                bool_list += li[j]
            coin += a_list[j]
    bool_list = set(bool_list)
    if len(bool_list) != n:
        continue
    min_coin = min(min_coin,coin)

if min_coin == 10**10:
    print(-1)
else:
    print(min_coin)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_list = []
li = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c = list(map(int,input().split()))
    for j in range(b):
        c[j] -= 1
    li.append(c)

min_coin = 10**10

for i in range(2**m):
    bool_list = [False]*n
    coin = 0
    for j in range(m):
        if (i >> j)&1:
            for k in li[j]:
                bool_list[k] = True
            coin += a_list[j]
    if False in bool_list:
        continue
    min_coin = min(min_coin,coin)

if min_coin == 10**10:
    print(-1)
else:
    print(min_coin)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(x) for x in input().split()]

a_list = []
k_list = []
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    c_list = [int(x) for x in input().split()]

    a_list.append(a)

    k = 0
    for c in c_list:
        k += 1 << (c - 1)
    k_list.append(k)

k_all = 2 ** n - 1

a_sum_max = 10 ** 8 + 1
a_sum = a_sum_max

for i in range(2 ** m):
    a = 0
    k = 0
    for j in range(m):
        if (i >> j) & 1 == 1:
            a += a_list[j]
            k |= k_list[j]

    if k == k_all and a < a_sum:
        a_sum = a

ans = a_sum if a_sum < a_sum_max else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

ans = DP[M-1][(1 << N)-1]
if ans == inf:
	print(-1)
else:
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline=sys.stdin.buffer.readline
n,m=map(int,readline().split())
dp=[10**10]*(1<<n)
dp[0]=0
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()))
for i in range(1<<n):
    for  (a,b),d in zip(ab,c):
        s=i|d
        dp[s]=min(dp[s],dp[i]+a)
ans=dp[-1]
if ans==10**10:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
graph = [None] * m
for i in range(m):
  a, b = map(int, sys.stdin.readline().split())
  res = 0
  for c in map(int, sys.stdin.readline().split()):
    res |= 1 << (c - 1)
    graph[i] = (a, res)


def main():
  dp = [[0] * (1 << n) for _ in range(m + 1)]
  for i in range(1, 1 << n):
    dp[0][i] = inf

  for i in range(m):
    for j in range(1 << n):
      dp[i+1][j] = min(dp[i][j ^ (j & graph[i][1])] + graph[i][0], dp[i][j])

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

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
trs=[]
for _ in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cnt=0
  for i in range(b):
    cnt+=2**(c[i]-1)
  trs.append((a,cnt))
dp=[10**9]*2**n
dp[0]=0
for i in range(2**n):
  for a,cnt in trs:
    dp[i|cnt]=min(dp[i]+a,dp[i|cnt])
if dp[2**n-1]!=10**9:
  print(dp[2**n-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    # 1-index
    k = [None]
    for _ in range(m):
        a, _ = mi()
        k.append([a, lmi()])

    d = 2 ** n
    dp = [[0] * d for _ in range(m + 1)]
    for j in range(1, d):
        dp[0][j] = inf
    for j in range(1, d):
        for i in range(1, m + 1):
            cost = k[i][0]
            able_to_open = k[i][1]
            mask = 0b0
            for num in able_to_open:
                mask |= (1 << (num - 1))
            # print(bin(mask))
            mask = ~mask
            # print(bin(mask))
            j_prime = j & mask
            dp[i][j] = min(dp[i-1][j], dp[i-1][j_prime] + cost)
    # print(dp)
    print(dp[m][d-1]) if dp[m][d-1] != inf else print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
inf=10**18
dp=[inf for _ in range(2**N)]
dp[0]=0;AB=[];C=[]
for _ in range(M):
    AB.append(tuple(map(int,input().split())))
    C.append(tuple(map(int,input().split())))
for ab,c in zip(AB,C):
    for v in range(2**N):
        nv=int(v)
        for k in c:
            bi=2**(k-1)
            if (v//bi)%2==0:
                nv+=bi
        dp[nv]=min(dp[nv],dp[v]+ab[0])
if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for v in range(2**N):
        nv=int(v)
        for c in C:
            bi=2**(c-1)
            if (v//bi)%2==0:
                nv+=bi
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N,M=map(int,input().split())
    dp=[float("inf") for _ in range(2**N)]
    dp[0]=0
    for _ in range(M):
        a,b=map(int,input().split())
        C=list(map(int,input().split()))
        for v in range(2**N):
            nv=copy.copy(v)
            for c in C:
                bi=2**(c-1)
                if (v//bi)%2==0:
                    nv+=bi
            dp[nv]=min(dp[nv],dp[v]+a)
    if dp[-1]==float("inf"):
        print(-1)
    else:
        print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for v in range(2**N):
        nv=copy.copy(v)
        for c in C:
            bi=2**(c-1)
            if (v//bi)%2==0:
                nv+=bi
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        cur = dp[i][state]
        if dp[i+1][used] > cur + A[i]:
            dp[i+1][used] = dp[i][state] + A[i]

        if dp[i+1][state] > cur:
            dp[i+1][state] = cur

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

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(
        M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        dp[i+1][used] = min(dp[i+1][used], dp[i][state] + A[i])

        dp[i+1][state] = min(dp[i+1][state], dp[i][state])

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
#len(dp)==16　（2**n）　扉の開閉状態
#dp: その開閉状態を実現するための鍵の値段の最小値

#それぞれの鍵について
for i in range(m):
  a,b = map(int,input().split())
  #x: 開く扉の番号
  #2**(1-1)==000000000001   2**(12-1)==100000000000
  #sは　100010111000みたいなやつ（その鍵で開く扉が１）
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    #| : or
    #（ある状態＋その鍵を使って開けられるやつ）の状態　　もともとの数値か、鍵を使うか
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#ABC142-E Get Everything
"""
宝箱の制約が12個なので、これの状態を集合とする.
鍵をcost昇順に並べる。
ある鍵について、新たに埋められる場所が存在するなら、その鍵を使ってみる
"""
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
INF = 10**10
cost_len_key = []
for i in range(m):
    a,b = map(int,readline().split())
    lst1 = list(map(int,readline().split()))
    res = 0
    for j in lst1:
        res += 1<<(j-1)
    cost_len_key.append([a,INF-b,res])

cost_len_key.sort()

#dp:状態s(か、s以上)の箱を開けた場合の最小コスト
dp = [INF for _ in range(1<<n)]

def rec(s,v,dp):
    if dp[s] < INF:
        return dp[s]
    if s == (1<<n) -1:
        return 0
    
    res = INF
    for u in range(v,m):
        if cost_len_key[u][2] & s != cost_len_key[u][2]: #sにはない場所が存在するなら
            res = min(res,rec(cost_len_key[u][2] | s,v+1,dp)
            +cost_len_key[u][0])
    dp[s] = res
    return res
res = rec(0,0,dp)
print(res if res < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            tar = int(key[j], 0) | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
cost = []
key = []
inf = int(1e9)
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    cost.append(a)
    cnt = 0
    for j in range(1,n+1):
        if j in c:
           cnt += 2**(n-j)
    key.append(bin(cnt))
dp = [inf]*(2**n)
for i in range(m):
    dp[int(key[i],0)] = min(cost[i],dp[int(key[i],0)])
for i in range(2**n):
    if dp[i] != inf:
        for j in range(m):
            k = int(key[j], 0)
            tar = k | i
            dp[tar] = min(dp[tar], dp[i] + cost[j])
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0
keys = []

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

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

Submission status: Time Limit Exceeded

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

INF = 10**18

# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a, _), c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        dp[i | c] = min(dp[i | c], dp[i] + a)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
keys = []
INF = 10 ** 5 * 12
dp = [INF] * (1 << n)
dp[0] = 0

for _ in range(m):
    a, b = map(int, input().split())
    s = 0
    for c in list(map(int, input().split())):
        s |= 1 << (c - 1)
    keys.append([s, a])

for s in range(1 << n):
    for i in range(m):
        to = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[to] = min(dp[to], cost)

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

Submission status: Time Limit Exceeded

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

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(int, input().split()):
        k |= (1 << (i - 1))
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        dp[state | k] = min(dp[state | k], dp[state] + a)

ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0
#dp[i]は、iを取るために必要な最小費用
for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def open(box, key):
    n = 0
    for i in range(N):
        if (box>>i & 1) - (key>>i & 1) >= 1:
            n += 2**i
    return n
N, M = map(int, input().split())
INF = 10**8+1
dp = [[INF]*2**(N+1) for i in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
key = []
for i in range(M):
    a, b= map(int, input().split())
    n = 0
    c = list(map(int, input().split()))
    for i in range(b):
        n += 2**(c[i]-1)
    key.append((a,n)) 
for i in range(1,M+1):
    for j in range(2**(N+1)):
        dp[i][j] = min(dp[i-1][j], dp[i-1][open(j, key[i-1][1])]+key[i-1][0])
if dp[M-1][2**(N+1)-1] == INF:
    dp[M-1][2**(N+1)-1] = -1
print(dp[M-1][2**(N+1)-1])

Submission status: Time Limit Exceeded

Solution code:
def open(box, key):
    n = 0
    for i in range(N):
        if (box>>i & 1) - (key>>i & 1) >= 1:
            n += 2**i
    return n
N, M = map(int, input().split())
INF = 10**10
dp = [[INF]*2**(N+1) for i in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0
key = []
for i in range(M):
    a, b= map(int, input().split())
    n = 0
    c = list(map(int, input().split()))
    for i in range(b):
        n += 2**(c[i]-1)
    key.append((a,n)) 
for i in range(1,M+1):
    for j in range(2**(N+1)):
        dp[i][j] = min(dp[i-1][j], dp[i-1][open(j, key[i-1][1])]+key[i-1][0])
if dp[M-1][2**(N+1)-1] == INF:
    dp[M-1][2**(N+1)-1] = -1
print(dp[M-1][2**(N+1)-1])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc142/tasks/abc142_e
# このナップサックdpは面白い！
# 配るdpをイメージするとわかりやすい
# dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
# bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


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


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) # i番目を取る
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) #i番目を取らない
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

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

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

for i, bit in product(range(M), 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)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = []
key = []
for i in range(m):
    d = [float('inf')]*(2**n)
    d[0] = 0
    dp.append(d)
for i in range(m):
    cost,num = map(int,input().split())
    if num == 1:
        t = int(input())
        key.append([cost,2**(t-1)])
    else:
        p = list(map(int,input().split()))
        cur = 0
        for i in range(len(p)):
            cur += 2**(p[i]-1)
        key.append([cost,cur])
for i in range(m):
    for j in range(2**n):
        if i != 0:
            dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0])
if dp[m-1][2**n-1] != float('inf'):
    print(dp[m-1][2**n-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = sum([1 << (i - 1) for i in map(int, input().split())])
    keys.append([a, bits])

dp = [INF] * (2 ** N + 10)
dp[0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[j|keys[i][1]] = min(dp[j|keys[i][1]], dp[j]+keys[i][0])
print(dp[2 ** N - 1] if dp[2 ** N - 1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [None]*m
c = [0]*m
for i in range(m):
    a[i], b = map(int, input().split())
    ls = list(map(int,input().split()))
    for j in ls:
        c[i] |= 1<<(j-1)
n2 = 1<<n
dp = [1e9]*(n2)
dp[0] = 0
for i in range(m):
    for S in range(n2):
        dp[S|c[i]] = min(dp[S|c[i]], dp[S]+a[i])
if dp[(n2)-1] < 1e9:
    print(dp[(n2)-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = sum([1 << (i - 1) for i in map(int, input().split())])
    keys.append([a, bits])

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

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [None]*m
c = [0]*m
for i in range(m):
    a[i], b = map(int, input().split())
    ls = list(map(int,input().split()))
    for j in ls:
        c[i] |= 1<<(j-1)

dp = [[1e9]*(1<<n) for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for S in range(1<<n):
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])
        dp[i+1][S|c[i]] = min(dp[i+1][S|c[i]], dp[i][S]+a[i])
if dp[m][(1<<n)-1] < 1e9:
    print(dp[m][(1<<n)-1])
else:
    print(-1)