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 copy

inf = 10 ** 8


N,M = map(int,input().split())

def tolist(n):
    nn = n
    ret = [0] * N
    for i in range(N):
        ret[i] = nn % 2
        nn //= 2
    return ret

def tonum(l):
    ret = 0
    for i in range(N):
        ret += l[i] * (2**i)
    return ret

def union(l1,l2):
    ret = [0] * N
    for i in range(N):
        ret[i] = min(l1[i] + l2[i],1) 
    return tonum(ret)



cost = [0] * M
data = [[0]*N for i in range(M)]

for i in range(M):
    a,b = map(int,input().split())
    cost[i] = a
    c = list(map(int,input().split()))
    for x in c:
        x -= 1
        data[i][x] = 1

dp = [inf]*(2**N)


for j in range(2**N):
    if union(tolist(j),data[0]) == tonum(data[0]):
        dp[j] = cost[0]

dp[0] = 0

for i in range(1,M):
    #print(dp)
    for j in range(2**N):
        #print(dp)
        ###このjは一つ前のiのものであることに注意
        l = tolist(j)
        dp[union(l,data[i])] = min(dp[union(l,data[i])], dp[j]+cost[i])
        

#print(dp)
if dp[2**N -1] == inf:
    print(-1)
else:
    print(dp[2**N -1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nが小さいのでdfs
N, M = lr()
keys = [None] * (M+1) # 1-indexed
for i in range(M):
    a, b = lr()
    c = set(lr())
    keys[i+1] = (a, c)

def dfs(m, fee, open):
    global answer
    if m == M+1:
        if len(open) == N:
            answer = min(answer, fee)
    else:
        new_box = keys[m][1]
        if len(new_box - open) > 0:
            dfs(m+1, fee+keys[m][0], open.union(keys[m][1]))
        dfs(m+1, fee, open)

INF = 10 ** 10
answer = INF
dfs(1, 0, set())
print(-1 if answer == INF else answer)
# 38

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nが小さいのでdfs
N, M = lr()
keys = [None] * (M+1) # 1-indexed
for i in range(M):
    a, b = lr()
    c = set(lr())
    keys[i+1] = (a, c)

def dfs(m, fee, open):
    global answer
    if m == M+1:
        if len(open) == N:
            answer = min(answer, fee)
    else:
        dfs(m+1, fee+keys[m][0], open.union(keys[m][1]))
        dfs(m+1, fee, open)

INF = 10 ** 10
answer = INF
dfs(1, 0, set())
print(-1 if answer == INF else answer)
# 38

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    cs = list(map(int, input().split()))
    c = 0
    for c_ in cs:
        c += 1 << (c_-1)
    C[i] = c

dp = [float('inf')]*(1 << n)
dp[0] = 0
for i in range(1 << n):
    for j in range(m):
        c = C[j]
        dp[i|c] = min(dp[i|c], dp[i]+A[j])

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

Submission status: Time Limit Exceeded

Solution code:

n, m = map(int, input().split())

dp = [[float("inf") for _ in range(2 ** n)] for i in range(m + 1)]
dp[0][0] = 0

pattern = {0}

for i in range(1, m+1):
  ai, bi = map(int, input().split()) 
  ci_bit = sum(2 ** (cij - 1) for cij in map(int, input().split()))
  new_pattern = set()
  for j in pattern:
    dp[i][j | ci_bit] = min(dp[i][j | ci_bit], dp[i-1][j] + ai)
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    new_pattern.add(j | ci_bit)
  pattern |= new_pattern


print(-1 if dp[m][2**n - 1] == float("inf") else dp[m][2**n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M = MI()
	dp = [float("inf")] * (2**N)
	dp[0] = 0
	for _ in range(M):
		a,b = MI()
		cc = LI()
		state = 0
		for c in cc:
			c -= 1
			state += (1 << c)
			for i in range(2**N):
				if(dp[i]!=float("inf")):
					dp[i|state] = min(dp[i|state], dp[i]+a)
	if(dp[-1]!=float("inf")):
		print(dp[-1])
	else:
		print(-1)


main()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = [[]for _ in range(M)]
    C = [0]*M
    for i in range(M):
        A[i], b = LI()
        c = LI()
        for j in range(b):
            C[i] += 2**(c[j]-1)
    loop = 2**N
    dp = [[inf]*loop for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for l in range(loop):
            dp[i + 1][l] = min(dp[i + 1][l],dp[i][l])
            next = l|C[i]
            if next==l:
                continue
            dp[i+1][next] = min(dp[i+1][next],dp[i][l] + A[i])
    ans = dp[M][loop-1]
    if ans==inf:
        print(-1)
    else:
        print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[0]*M
import heapq
import collections
from itertools import permutations
table=collections.defaultdict(list)
AC=[[0,0] for i in range(M)]
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  AC[i][0]=a
  tmp=set(map(int,input().split()))
  for x in tmp:
    AC[i][1] |= 1<<(x-1)
dp=[10**9]*(2**N)
dp[0]=0

for i in range(1,2**N):
  k=0
  s=set()
  for j in range(1,i):
    if i & j == j:
      dp[i]=min(dp[i],dp[j]+dp[i^j])
  for a,c in AC:
    if c&i == i:
      dp[i]=min(dp[i],a)
  #print(dp[i],bin(i))
  
if dp[-1]==10**9:
  print(-1)
else:
  print(dp[-1])
#print(dp)

  
  
#print(AC)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(map(int, input().split()))
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

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())

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)

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.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)

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.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)

Submission status: Time Limit Exceeded

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

def main():
  n, m = map(int, input().split())
  U = 2**n
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c |= 1<<(l-1)
    for j in range(U):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

  if dp[m-1][2**n-1] == float("inf"):
    print(-1)
  else:
    print(dp[m-1][2**n-1])
    
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
  n, m = map(int, input().split())
  U = 2**n
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c += 2**(l-1)
    for j in range(U):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

  if dp[m-1][2**n-1] == float("inf"):
    print(-1)
  else:
    print(dp[m-1][2**n-1])
    
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
  n, m = map(int, input().split())
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c += 2**(l-1)
    for j in range(2**n):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

  if dp[m-1][2**n-1] == float("inf"):
    print(-1)
  else:
    print(dp[m-1][2**n-1])
    
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (c - 1) for c in list(map(int, input().split()))])
    keys.append([a, c])


# dp[bs] := 鍵の集合bsを手に入れるのに必要な最小費用
dp = [float('inf')] * (1 << N)
dp[0] = 0

for i, (cost, key) in enumerate(keys):
    for bs in range(1 << N):
        dp[bs | key] = min(dp[bs | key], dp[bs] + cost)

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [INF] * (2 ** N)
dp[0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        dp[j | k] = min(dp[j | k], dp[j] + a)

ans = dp[2 ** N - 1] if dp[2 ** N - 1] < INF else -1
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int,input().split())
    INF = 10**7
    k = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for i in c:
            bit += 2**(i-1)
        k.append((a,bit))
    dp = [[INF for _ in range(1<<N)] for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        a,bit = k[i]
        for j in range(1<<N):
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
            dp[i+1][j|bit] = min(dp[i+1][j|bit],dp[i][j|bit],dp[i][j]+a)
    
    print(dp[-1][-1] if dp[-1][-1] != INF else -1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,M = map(int,input().split())
    INF = 10**7
    k = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for i in c:
            bit += 2**(i-1)
        k.append((a,bit))
    dp = np.full((M+1,1<<N),INF, dtype=np.int64)
    dp[0][0] = 0
    for i in range(M):
        a,bit = k[i]
        for j in range(1<<N):
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
            dp[i+1][j|bit] = min(dp[i+1][j|bit],dp[i][j|bit],dp[i][j]+a)
    
    print(dp[-1][-1] if dp[-1][-1] != INF else -1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

N, M=map(int, input().split())
dp = [INF] * 2**N
dp[0] = 0
for i in range(M):
    A, B = map(int, input().split())
    C = sum([2**(int(i)-1) for i in input().split()])
    for s in range(2**N):
        t = s | C
        dp[t] = min(dp[t], dp[s] + A)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
A=[]
C=defaultdict(lambda: 10**5)
for _ in range(m):
    a,_=map(int,input().split())
    c=tuple([int(i) for i in input().split()])
    
    if a < C[c]:
        C[c]=a
    A.append(a)
A=list(C.values())
C=list(C.keys())
full = set(range(1,n+1))
bit=[]
n = len(C)
min_ = sum(A)
flag = True
for i in range(1,2 ** n):
    s = set()
    cost = 0
    for j in range(n):  
        if ((i >> j) & 1):
            s = s | set(C[j])
            cost += A[j]
    #print(s,bag,cost)
    if s == full:
        min_ = min(min_,cost)
        flag =False
if flag:
    print(-1)
else:
    print(min_)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
A=[]
C=defaultdict(lambda: 10**5)
for _ in range(m):
    a,_=map(int,input().split())
    c=tuple([int(i) for i in input().split()])
    
    if a < C[c]:
        C[c]=a
    A.append(a)
A=list(C.values())
C=list(C.keys())
full = set(range(1,n+1))
bit=[]
n = len(C)
min_ = sum(A)
flag = True
for i in range(1,2 ** n):
    bag = []
    cost = []
    for j in range(n):  
        if ((i >> j) & 1):
            bag.append(C[j])
            cost.append(A[j])
    s=set()
    for l in bag:
        s = s | set(l)
    if s == full:
        cost = sum(cost)
        min_ = min(min_,cost)
        flag =False
if flag:
    print(-1)
else:
    print(min_)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
C=[]
for _ in range(m):
    a,_=map(int,input().split())
    C.append([int(i) for i in input().split()])
    A.append(a)

full = set(range(1,n+1))
bit=[]
n = len(C)
min_ = sum(A)
flag = True
for i in range(1,2 ** n):
    bag = []
    cost = []
    for j in range(n):  
        if ((i >> j) & 1):
            bag.append(C[j])
            cost.append(A[j])
    s=set()
    for l in bag:
        s = s | set(l)
    if s == full:
        cost = sum(cost)
        min_ = min(min_,cost)
        flag =False
if flag:
    print(-1)
else:
    print(min_)

Submission status: Time Limit Exceeded

Solution code:



N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    # c[i]で開けられる宝箱はbitの１が立っている部分
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9
# m番目の鍵をつかって、開けた宝箱がbitの状態になったときの、最小コスト
dp = [INF] * (1 << N)
dp[0] = 0


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

print(dp[-1] if dp[-1] < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    c_ = list(map(int, input().split()))
    c = 0
    for v in c_:
        c += 2**(v-1)
    abc.append([a, b, c])

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

for i in range(m):
    dp[i][0] = 0

for i in range(m):
    for j in range(1 << n):
        s = j | abc[i][2]
        dp[i+1][s] = min(dp[i+1][s], dp[i][j] + abc[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
if dp[-1][-1] == INF:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ab = []
c = []
def bit(st):
    ls = list(st)
    res = 0
    for elem in ls:
        res += 2**(elem-1)
    return res

for i in range(M):
    ab.append(list(map(int,input().split())))
    c.append(set(map(int,input().split())))
dp = [10**6]*(2**N)
dp[0] = 0
for i in range(M):
    for j in range(2**N):
        dp[bit(c[i]) | j] = min(dp[bit(c[i]) | j], dp[j]+ab[i][0])
if dp[2**N-1] == 10**6:
    print(-1)
else:
    print(dp[2**N-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

dp=[[[[[[[[[[[[10**9]*2 for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(2)]

dp[0][0][0][0][0][0][0][0][0][0][0][0]=0

for _ in range(M):
    al,bl=map(int,input().split())
    temp=[0]*12
    cl=list(map(int,input().split()))
    for item in cl:
        temp[item-1]=1
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        for j in range(2):
                                            for k in range(2):
                                                for l in range(2):
                                                    if dp[a][b][c][d][e][f][g][h][i][j][k][l]!=10**9:
                                                        dp[max(a,temp[0])][max(b,temp[1])][max(c,temp[2])][max(d,temp[3])][max(e,temp[4])][max(f,temp[5])][max(g,temp[6])][max(h,temp[7])][max(i,temp[8])][max(j,temp[9])][max(k,temp[10])][max(l,temp[11])]=min(dp[max(a,temp[0])][max(b,temp[1])][max(c,temp[2])][max(d,temp[3])][max(e,temp[4])][max(f,temp[5])][max(g,temp[6])][max(h,temp[7])][max(i,temp[8])][max(j,temp[9])][max(k,temp[10])][max(l,temp[11])],dp[a][b][c][d][e][f][g][h][i][j][k][l]+al)
                                                        
                            
    #print(temp)

fa=[0]*12
for i in range(N):
    fa[i]=1

#print(fa)
if dp[fa[0]][fa[1]][fa[2]][fa[3]][fa[4]][fa[5]][fa[6]][fa[7]][fa[8]][fa[9]][fa[10]][fa[11]]==10**9:
    print(-1)
else:
    print(dp[fa[0]][fa[1]][fa[2]][fa[3]][fa[4]][fa[5]][fa[6]][fa[7]][fa[8]][fa[9]][fa[10]][fa[11]])

Submission status: Time Limit Exceeded

Solution code:
import itertools

# 長さnの配列からいくつか (0個を含む) 選んで，それをsetにして返すイテレータ
# 2進数 (bit列) と同一視する．つまり，
class BitIterator:
    def __init__(self, array):
        self.array = array
        self.n = len(array)
        self.i = 0
        self.imax = 2**self.n

    def __iter__(self):
        return self

    def __next__(self):

        if self.i == self.imax:
            raise StopIteration()
        
        # bin(self.i)のj+1桁目が1 = i&1<<j!=1 -> retにself.array[j-1]を追加
        ret = set()
        for j in range(self.n):
            # print(bin(self.i), bin(1<<j), self.i&(1<<j)!=0)
            if self.i&(1<<j)!=0:
                ret.add(self.array[j])
        
        self.i += 1
        return frozenset(ret)


# for _ in BitIterator(range(2)):
#     print(_)
        

N,M = map(int,input().split())
a = []
b = []
c = []
for _ in range(M):
    row = list(map(int,input().split()))
    a.append(row[0])
    b.append(row[1])
    row = list(map(int,input().split()))
    # 1ひいておく
    row = list(map(lambda x: x-1, row))
    c.append(row)


# 集合の最適な選び方を探すDP (動的計画法)
dp = {}

# 初期化
# 全てコスト無限大としておく
for S in BitIterator(range(N)):
    dp[S] = float('inf')
# 空集合 = どの箱も開けない ときの最適コストは0
dp[frozenset()] = 0

# 遷移させながら最適コストを計算
for S in BitIterator(range(N)):
    # 状態Sの遷移 = 鍵を1つ買う
    for key in range(M):
        # 遷移先 = S | c[key][:]
        T = frozenset(S | set(c[key]))
        # 遷移先のコスト
        cost= dp[S] + a[key]

        dp[T] = min(dp[T], cost)

# すべての箱を開けるのに必要なコスト
cost = dp[frozenset(range(N))]
if cost == float('inf'):
    print(-1)
else:
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
A = {S:{tuple(G[j][1]):[0] for j in range(M)} for S in product((0,1),repeat=N) }
for S in product((0,1),repeat=N):
    for j in range(M):
        B = [0 for _ in range(N)]
        for x in G[j][1]:
            B[x-1] = 1
        C = list(S[:])
        for i in range(N):
            if C[i]==1 and B[i]==1:
                C[i] = 0
        A[S][tuple(G[j][1])] = tuple(C)
INFTY = 10**11
dp = {j:{S:INFTY for S in product((0,1),repeat=N)} for j in range(M+1)}
for j in range(M+1):
    dp[j][tuple([0 for _ in range(N)])] = 0
for j in range(M):
    for S in product((0,1),repeat=N):
        dp[j+1][S] = min(dp[j][S],dp[j][A[S][tuple(G[j][1])]]+G[j][0])
s = tuple([1 for _ in range(N)])
a =dp[M][s]
if a>=INFTY:
    print(-1)
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
INFTY = 10**11
dp = {j:{S:INFTY for S in product((0,1),repeat=N)} for j in range(M+1)}
for j in range(M+1):
    dp[j][tuple([0 for _ in range(N)])] = 0
for j in range(M):
    for S in product((0,1),repeat=N):
        A = [0 for _ in range(N)]
        for x in G[j][1]:
            A[x-1] = 1
        B = list(S[:])
        for i in range(N):
            if B[i]==1 and A[i]==1:
                B[i] = 0
        dp[j+1][S] = min(dp[j][S],dp[j][tuple(B)]+G[j][0])
s = tuple([1 for _ in range(N)])
a =dp[M][s]
if a>=INFTY:
    print(-1)
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()[:-1]

def num2bi(x, k):
  return format(x, '0'+str(k)+'b')

def bi2num(b):
  return int(b, 2)

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
dp[0][0]=0
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      jstr=list(num2bi(j, N))
      for k in range(b):
        if jstr[c[k]-1]=='0':
          jstr[c[k]-1]='1'
          
      tmp=bi2num(''.join(jstr))
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def num2bi(x, k):
  return format(x, '0'+str(k)+'b')

def bi2num(b):
  n=len(b)
  i=1
  out=0
  while i<n+1:
    out+=int(b[-i])*pow(2, i-1)
    i+=1
  return out

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
dp[0][0]=0
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      jstr=list(num2bi(j, N))
      for k in range(b):
        if jstr[c[k]-1]=='0':
          jstr[c[k]-1]='1'
          
      tmp=bi2num(''.join(jstr))
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [inf for i in range(2**N)]
dp[0] = 0
for i in range(1,M+1):
    dp[C[i]] = min(dp[C[i]],A[i])
    for j in range(2**N):
        k =  j|C[i]
        dp[k] = min(dp[k],dp[j]+A[i])
if dp[2**N-1] == inf:
    dp[2**N-1] = -1
print(dp[2**N-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [0]
C = [0] 
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    x = 0
    for j in range(1,N+1):
        if j in c:
            x += 2**(j-1)
    C.append(x)
inf = 10**9
dp = [[inf for i in range(M+1)] for i in range(2**N)]
dp[0][0] = 0
for i in range(2**N):
    for j in range(1,M+1):
        if i - C[j] < 0:
            dp[i][j] = min(dp[i][j-1],dp[i][j])
            continue
        for k in range(0,i+1):
            if k|C[j] == i:
                dp[i][j] = min(dp[i][j],dp[k][j-1]+A[j])
            dp[i][j] = min(dp[i][j],dp[i][j-1])
if dp[2**N-1][M] == inf:
    dp[2**N-1][M] = -1
print(dp[2**N-1][M])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = []
v = 0
for _ in range(M):
    a, b = map(int, input().split())
    l = sum([1 << (int(v) - 1) for v in input().split()])
    L.append([a, b, l])
    v = v | l
if v != (1 << N) - 1:
     print(-1)
     exit()

dp = [[10 ** 18 for _ in range(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] = min(dp[i + 1][j], dp[i][j])

          dp[i + 1][j | L[i][2]] =  min(dp[i + 1][j | L[i][2]], dp[i][j] + L[i][0])

print(dp[M][(1 << N) - 1])