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: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [None]
c = [None]
for i in range(m):
    ab.append(list(map(int, input().split())))
    c.append(list(map(int, input().split())))

c_bit = [None]
for li in c[1:]:
    b = 0
    for e in li:
        b += 2 ** (e - 1)
    c_bit.append(b)

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

for i in range(1, m + 1):
    state = c_bit[i]
    dp[0][state] = ab[i][0]

#print(*dp, sep="\n")
#print()

for j in range(1, 2 ** n):
    for i in range(1, m + 1):
        state = j | c_bit[i]
        mn = min(dp[i-1][state], dp[i-1][j] + ab[i][0])
        dp[i][state] = min(mn, dp[i][state])
        if dp[i-1][j] != float("inf") and dp[i][j] == float("inf"):
            dp[i][j] = dp[i-1][j]

#print(*dp, sep="\n")

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=2**N
l=[float("inf")]*L
l[0]=0
r=(1,2,4,8,16,32,64,128,256,512,1024,2048)
for i in range(M):
    s=0
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    for j in c:
        s+=r[j-1]
    for j in range(L):
        l[j|s]=min(l[j|s],l[j]+a)
if l[-1]=="inf":
    print(-1)
else:
    print(l[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
L = []
C = []
for i in range(M):
    L.append([int(l) for l in input().split()])
    C.append([int(c) for c in input().split()])
    
dp = [10**8+1 for j in range(2**N)]
dp[0] = 0

for i in range(1, M+1):
    temp = 0
    for k in range(len(C[i-1])):
        temp += 2**(C[i-1][k]-1)
    for j in range(2**N):
        if i == 1:
            if j | temp == temp and j != 1:
                dp[j] = L[i-1][0]

        else:
            dp[temp | j] = min(dp[temp | j], dp[j]+L[i-1][0])
      
if dp[-1] >= 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A=[0]*M
B=[0]*M
C=[]
for m in range(M):
    A[m],B[m] = map(int, input().split())
    C.append(list(map(int, input().split())))

keys=[[] for i in range(N)] #宝箱iを開けるのに必要な鍵
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    
keys2=[]
bought=[]
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys2.append(keys.pop(i))
    keys_num.pop(i)
for j in range(M):
    for k_list in keys2:
        if len(k_list) > 1 and set(k_list) <= set(bought):
            index=min(k_list,key=lambda k:A[k-1])
            k_list.remove(index)
            ans-=A[index-1]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
L = []
C = []
for i in range(M):
    L.append([int(l) for l in input().split()])
    C.append([int(c) for c in input().split()])
    
dp = [10**8+1 for j in range(2**N)]
dp[0] = 0

for i in range(1, M+1):
    temp = 0
    for k in range(len(C[i-1])):
        temp += 2**(C[i-1][k]-1)
    for j in range(2**N):
        if i == 1:
            if j | temp == temp:
                dp[j] = L[i-1][0]

        else:
            dp[temp | j] = min(dp[temp | j], dp[j]+L[i-1][0])
                
if dp[-1] >= 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
L = []
C = []
for i in range(M):
    L.append([int(l) for l in input().split()])
    C.append([int(c) for c in input().split()])
    
dp = [10**8+1 for j in range(2**N)]
dp[0] = 0

for i in range(M):
    temp = 0
    for k in range(len(C[i-1])):
        temp += 2**(C[i-1][k]-1)
    for j in range(2**N):
        if i == 1:
            if j | temp == temp:
                dp[j] = L[i-1][0]

        else:
            dp[temp | j] = min(dp[temp | j], dp[j]+L[i-1][0])
                
if dp[-1] >= 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A=[0]*M
B=[0]*M
C=[]
for m in range(M):
    A[m],B[m] = map(int, input().split())
    C.append(list(map(int, input().split())))

keys=[[] for i in range(N)] #宝箱iを開けるのに必要な鍵
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    
keys2=[]
bought=[]
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys2.append(keys.pop(i))
    keys_num.pop(i)
for j in range(M):
    for k_list in keys2:
        if len(k_list) > 1 and k_list in bought:
            index=min(k_list,key=lambda k:A[k-1])
            k_list.remove(index)
            ans-=A[index-1]
print(ans)

Submission status: Wrong Answer

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

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] < cost[i]+a[j]:
            cost[i|move2] = cost[i]+a[j]

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [None]
c = [None]
for i in range(m):
    ab.append(list(map(int, input().split())))
    c.append(list(map(int, input().split())))

c_bit = [None]
for li in c[1:]:
    b = 0
    for e in li:
        b += 2 ** (e - 1)
    c_bit.append(b)

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

for i in range(2 ** n):
    state = i & c_bit[1]
    if state == i and i != 0:
        dp[1][i] = ab[1][0]
    else:
        dp[1][i] = float("inf")

#print(*dp, sep="\n")
#print()

for i in range(2, m + 1):
    for j in range(1, 2 ** n):
        state = j | c_bit[i]
        mn = min(dp[i-1][state], dp[i-1][j] + ab[i][0])
        dp[i][state] = min(mn, dp[i][state])
        if dp[i-1][j] != float("inf") and dp[i][j] == float("inf"):
            dp[i][j] = dp[i-1][j]

#print(*dp, sep="\n")

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [None]
c = [None]
for i in range(m):
    ab.append(list(map(int, input().split())))
    c.append(list(map(int, input().split())))

c_bit = [None]
for li in c[1:]:
    b = 0
    for e in li:
        b += 2 ** (e - 1)
    c_bit.append(b)

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

for i in range(2 ** n):
    state = i & c_bit[1]
    if state == i:  # and i != 0:
        dp[1][i] = ab[1][0]
    else:
        dp[1][i] = float("inf")

#print(*dp, sep="\n")
#print()

for i in range(2, m + 1):
    for j in range(1, 2 ** n):
        state = j | c_bit[i]
        mn = min(dp[i-1][state], dp[i-1][j] + ab[i][0])
        dp[i][state] = min(mn, dp[i][state])
        if dp[i-1][j] != float("inf") and dp[i][j] == float("inf"):
            dp[i][j] = dp[i-1][j]

#print(*dp, sep="\n")

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [None]
c = [None]
for i in range(m):
    ab.append(list(map(int, input().split())))
    c.append(list(map(int, input().split())))

c_bit = [None]
for li in c[1:]:
    b = 0
    for e in li:
        b += 2 ** (e - 1)
    c_bit.append(b)

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

for i in range(2 ** n):
    state = i & c_bit[1]
    if state == i and i != 0:
        dp[1][i] = ab[1][0]
    else:
        dp[1][i] = float("inf")

#print(*dp, sep="\n")
#print()

for i in range(2, m + 1):
    for j in range(2 ** n):
        state = j | c_bit[i]
        mn = min(dp[i-1][state], dp[i-1][j] + ab[i][0])
        dp[i][state] = min(mn, dp[i][state])
        if dp[i-1][j] != float("inf") and dp[i][j] == float("inf"):
            dp[i][j] = dp[i-1][j]

#print(*dp, sep="\n")

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    
    li = list(map(int, input().split()))
    li2 = list(map(int, input().split()))    
    a.append([li,li2])
b = []
from collections import defaultdict
d = defaultdict(int)
#print(a)
for j in range(1,n+1):
    min1 = 10**5
    for i in range(len(a)):
        if   (j in a[i][1]):
            b.append(j)
            #print(b)
            #print(b.count(j)==1)
            if (j in b) and (b.count(j) == 1):
                #print((j in b) and (b.count(j) == 1))
                min1 = min(min1,int(a[i][0][0]))
                d[j] = min1
                #print(min1)
sum = 0
#print(d)
for v in d.values():
    sum += v
print(sum)

Submission status: Wrong Answer

Solution code:
# O(M + 4^N) 解
# 参考: https://twitter.com/ei1333/status/1177951676818325504

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [float("inf")] * (1<<N)
for _ in range(M):
    a, _ = map(int, input().split())
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        s |= 1 << c-1
    dp[s] = min(dp[s], a)
for i in range(1<<N):
    for j in range(1<<N):
        dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1]
print(ans if ans!=float("inf") else ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
dp=[10**18]*(2**(n))
ll=[0]*(n+1)
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=set([int(j) for j in input().split()])
    for j in tmp:
        ll[j]=1
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind+=2**(j-1)
    dp[ind]=x
if sum(ll)!=n:
    print(-1)
    exit()

for i in range(1,2**n):
    if dp[i]<=10**5:
        for j in range(i,2**n):
            dp[i|j]=min(dp[i|j],dp[i]+dp[j])

if dp[-1]!=10**18:
    print(dp[-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(1,None)]*n
    for x in c:
        l0[x-1] = slice(None,1)
        l1[x-1] = slice(None)
    dp[tuple([0]*n)] = 0
    dp = np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(1,2)]*n
    for x in c:
        l0[x-1] = slice(0,1)
        l1[x-1] = slice(None)
    dp = np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    p = 2**n
    dp = [10**7]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([2**(int(i)-1) for i in input().split()])
        for s in range(p):
                t = s|c
                if dp[t] > dp[s] + a:
                    dp[t] = dp[s] + a
    ans = dp[-1]
    if ans == float('inf'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(None)]*n
    l2 = [1]*n
    for x in c:
        l0[x-1] = 0
        l1[x-1] = 1
        l2[x-1] = slice(None)
    dp[tuple(l1)] = np.minimum(np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a), np.min(dp[tuple(l2)], )+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ac = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        if dp[t] < dp[s] + a:
            dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(None)]*n
    l2 = [1]*n
    for x in c:
        l0[x-1] = slice(0,1)
        l1[x-1] = slice(1,2)
        l2[x-1] = slice(None)
    dp[tuple(l1)] = np.minimum(np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a), np.min(dp[tuple(l2)], )+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(None)]*n
    l2 = [1]*n
    for x in c:
        l0[x-1] = slice(0,1)
        l1[x-1] = slice(1,2)
        l2[x-1] = slice(None)
    dp[tuple(l1)] = np.minimum(np.minimum(dp[tuple(l1)], dp[tuple(l0)]+a), np.min(dp[tuple(l2)], )+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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


def dfs(v, visited, G):
    visited[v] = True
    for nv in G[v]:
        if visited[nv]==False:
            dfs(nv, visited, G)


def main():
    N, M = map(int, input().split())
    A = []
    D = []
    for i in range(M):
        a, b = map(int, input().split())
        A.append(a)
        C = list(map(int, input().split()))
        d = 0
        for c in C:
            d = d | 1<<c-1
        D.append(d)
    # print(A)
    # print(D)

    dp = [[float('inf')]*(2**N) for _ in range(M)]
    dp[0][D[0]] = A[0]
    for i in range(1, M):
        for j in range(2**N - 1):
            dp[i][j] = dp[i-1][j]
            dp[i][j | D[i]] = min(dp[i-1][j | D[i]], dp[i-1][j] + A[i])
    
    # for i in range(M):
    #     print(dp[i])
    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: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    l1 = [slice(None)]*n
    l2 = [1]*n
    for x in c:
        l0[x-1] = 0
        l1[x-1] = 1
        l2[x-1] = slice(None)
    dp[tuple(l1)] = np.minimum(np.minimum(dp[tuple(l0)] + a, dp[tuple(l1)]), np.min(dp[tuple(l2)])+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input():
	return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
keys = []
for _ in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	keys.append([a, sum([1<<(x-1) for x in c])])
dp = [10**30 for _ in range(1<<n)]
dp[0] = 0

for c, v in keys:
	dp[v] = dp[0]+c

for i in range(1, n):
	for p in combinations(range(n), i):
		j = 0
		for q in p:
			j += (1<<q)
		for c, v in keys:
			dp[j|v] = min(dp[j|v], dp[j]+c)

if dp[(1<<n)-1] > 10**20:
	print(-1)
else:
	print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
d = [0]*m
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
print(dp[2**n-1])

Submission status: Wrong Answer

Solution code:
n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
d = [0]*m
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
print(dp[2**n-1])

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[INF for j in range(2**n)] for i in range(m+1)]

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

for i in range(m):
    a, b = map(int, input().split())
    c = map(int, input().split())

    k = 0
    for ci in c:
        ci -= 1
        k |= (1 << ci)
    for j in range(2**n):
        l = k | j
        dp[i+1][l] = min(dp[i][l], dp[i][j] + a)

if dp[m][2**n-1] == INF:
    print(-1)
else:
    print(dp[m][2**n-1])

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[INF for j in range(2**n)] for i in range(m+1)]

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

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    k = 0
    for ci in c:
        ci -= 1
        k |= (1 << ci)
    for j in range(2**n):
        l =  k| j
        dp[i+1][l] = min(dp[i][l], dp[i][j] + a)

if dp[m][2**n-1] == INF:
    print(-1)
else:
    print(dp[m][2**n-1])

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[INF for j in range(2**n)] for i in range(m+1)]

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

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    k = 0
    for ci in c:
        ci -= 1
        k |= (1 << ci)
    for j in range(2**n):
        k |= j
        dp[i+1][k] = min(dp[i][k], dp[i][j] + a)

if dp[m][2**n-1] == INF:
    print(-1)
else:
    print(dp[m][2**n-1])

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[INF for j in range(2**n)] for i in range(m+1)]

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

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    for j in range(2**n):
        k = 0
        for ci in c:
            ci -= 1
            k = k | (1 << ci)
        k = k | j
        dp[i+1][k] = min(dp[i][k], dp[i][j] + a)

if dp[m][2**n-1] == INF:
    print(-1)
else:
    print(dp[m][2**n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 2 << 31
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = [[0] * M for _ in range(2 ** 12)]
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if vis[i][j] == 1:
    continue
  vis[i][j] = 1
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    #dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    #Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(1000000)

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = []
B = []
C = []
for _ in range(M):
    ab = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(ab[0])
    B.append(ab[1])
    C.append([int(x) for x in stdin.readline().rstrip().split()])

opened = [False] * N
keys = [False] * M


def dfs(op, c, k):
    if False not in op:
        return c
    output = 10 ** 10
    for n in range(M):
        if not k[n]:
            kk = k
            kk[n] = True
            opp = op
            for x in C[n]:
                opp[x - 1] = True
            output = min(output, dfs(opp, c + A[n], kk))
    return output


ans = dfs(opened, 0, keys)
if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
C = []
S = set()
for j in range(M):
    a, b = map(int, input().split())
    A.append((j, a))
    c = list(map(int, input().split()))
    C.append(c)
    for i in c:
        S.add(i)
#print(C)      
if len(S) < N:
    print(-1)
    exit()
A.sort(key=lambda x: len(C[x[0]]))
A.sort(reverse=True)
A.sort(key=lambda x: x[1])
boxes = set()
answer = []
for a in A:
    if len(set(C[a[0]]) - boxes) >= 1:
        answer.append(a[0])
        for z in C[a[0]]:
            boxes.add(z)
# answerは必要な鍵のリスト　ただ被りがある
answer2 = []
boxes2 = set()

for a in answer[::-1]:
    if len(set(C[a]) - boxes2) >= 1:
        answer2.append(a)
        for z in C[a]:
            boxes2.add(z)
count = 0
A.sort(key=lambda x: x[0])
for a in answer2:
    count += A[a][1]

print(count)

Submission status: Wrong Answer

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

keys_dic = {}
treasures_list = [[] for x in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    keys_dic[i+1] = a
    for treasure in c:
        treasures_list[treasure-1].append(i+1)

ok = 10**8
ng = 0

def can_open_all_treasure(money):
    total_cost = 0
    used_keys = []
    for treasure in treasures_list:
        if len(treasure) == 0:
            print(-1)
            exit()
        else:
            min_cost = 10**6
            for openable_key in treasure:
                if openable_key in used_keys:
                    used_keys.append(openable_key)
                    min_cost = 0
                    continue
                else:
                    if keys_dic[openable_key] <= min_cost:
                        min_key = openable_key
                        min_cost = keys_dic[openable_key]
                    # min_cost = min(keys_dic[openable_key], min_cost)
            total_cost += min_cost
            used_keys.append(min_key)

    if money >= total_cost:
        return True
    else:
        return False

while ok - ng > 1:
    mid = (ok + ng) // 2
    if can_open_all_treasure(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A=[0]*M
B=[0]*M
C=[]
for m in range(M):
    A[m],B[m] = map(int, input().split())
    C.append(list(map(int, input().split())))

keys=[[] for i in range(N)]
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    
keys2=[]
bought=[]
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys2.append(keys.pop(i))
    keys_num.pop(i)
for j in range(M):
    for k_list in keys2:
        if len(k_list) > 1 and k_list in bought:
            index=min(k_list,key=lambda k:A[k-1])
            ans-=A[index-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
dp=[10**18]*(2**(n))
ll=[0]*(n+1)
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=set([int(j) for j in input().split()])
    for j in tmp:
        ll[j]=1
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind+=2**(j-1)
    dp[ind]=x
if sum(ll)!=n:
    print(-1)
    exit()

for i in range(1,2**n):
    for j in range(i,2**n):
        dp[i|j]=min(dp[i|j],dp[i]+dp[j])

if dp[-1]!=10**18:
    print(dp[-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


import numpy as np

N,M=acinput()

y=[[] for i in range(N+1)]
for i in range(M):
    a,b=acinput()
    c=acinput()
    c_bl=np.zeros(N+1)
    for sc in c:
        c_bl[sc]=1
        y[sc].append({"cost":a,"c":c_bl})

    

state=np.zeros(N+1)
dp=[-1 for i in range(N+1)]
dp[0]=0

for i in range(1,N+1):
    if np.all(state[1:(i+1)])>0:
        dp[i]=dp[i-1]
        continue
    
    mincost=10**9
    minkey=-1
    for k,sy  in enumerate(y[i]):
        if sy["cost"]<mincost:
            mincost=sy["cost"]
            minkey=k
    if minkey>=0:
        state+=y[i][minkey]["c"]
    else:
        dp[-1]=-1
        break
    dp[i]=dp[i-1]+mincost

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A=[0]*M
B=[0]*M
C=[]
for m in range(M):
    A[m],B[m] = map(int, input().split())
    C.append(list(map(int, input().split())))

keys=[[] for i in range(N)]
keys_num=[0]*N
for i,c_list in enumerate(C):
    for c in c_list:
        keys[c-1].append(i+1)
        keys_num[c-1]+=1
if min(keys_num)==0:
    print(-1)
    exit()
    
    
keys2=[]
bought=[]
ans=0
while len(keys_num)>0:
    i=keys_num.index(min(keys_num))
    K=keys[i]
    index=min(K,key=lambda k:A[k-1])
    if index in bought:
        pass
    else:
        ans+=A[index-1]
        bought.append(index)
    keys2.append(keys.pop(i))
    keys_num.pop(i)
for k_list in keys2:
    if len(k_list) > 1 and k_list in bought:
        index=min(k_list,key=lambda k:A[k-1])
        ans-=A[index-1]
print(ans)

Submission status: Wrong Answer

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

keys_dic = {}
treasures_list = [[] for x in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    keys_dic[i+1] = a
    for treasure in c:
        treasures_list[treasure-1].append(i+1)

ok = 10**8
ng = 0

def can_open_all_treasure(money):
    total_cost = 0
    used_keys = []
    for treasures in treasures_list:
        #used_keys = []
        if len(treasures) == 0:
            print(-1)
            exit()
        else:
            min_cost = 10**6
            for openable_key in treasures:
                if openable_key in used_keys:
                    min_cost = 0
                else:
                    min_cost = min(keys_dic[openable_key], min_cost)
            total_cost += min_cost
            used_keys.append(openable_key)

    if money >= total_cost:
        return True
    else:
        return False

while ok - ng > 1:
    mid = (ok + ng) // 2
    if can_open_all_treasure(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
#import numpy as np
N,M=list(map(int,input().split()))
#cost=[]
query=[]
check=[0 for _ in range(N)]
flag=False
for i in range(M*2):
    tmp=list(map(int,input().split()))
    if i%2==0:
        cost=tmp[0]
    else:
        cal=[0 for _ in range(N+1)]
        cal[0]=cost
        for j in tmp:
            cal[j]=1
        query.append(cal)
            
            

error_check=[0 for _ in range(N)]
for i in query:
    for j in range(N):
        error_check[j]+=i[j]
if 0 in error_check:
    print(-1)
    exit()
query=sorted(query, key=lambda x: x[0])
#print(np.array(query))
total=0
backup=check.copy()
cost=0
for i in range(N):
    if check[i]>0:
        continue
    for each in query:
        if each[i+1]==1:
            cost+=each[0]
            for j in range(N):
                check[j]+=each[j+1]
            break
    for each in query:
        if cost<each[0]:
            break
        else:
            c=sum(each[1:i+2])
            if c==i+1:
                check=backup.copy()
                cost=each[0]
                for j in range(N):
                    check[j]+=each[j+1]
                break
    backup=check.copy()
print(cost)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def string_lines_scanner(N):
    for n in range(N):
        a, b = input().split()
        cs = [c for c in input().split()]
        yield int(a), int(b), cs

def main():
    N, M = input().split()
    N, M = int(N), int(M)
    btoc = {}
    btok = {}
    ktoc = {}
    for k, (cost, box_num, cs) in enumerate(string_lines_scanner(M)):
        ktoc[k+1] = cost
        for bn in range(box_num):
            box_no = cs[bn]
            if btoc.get(box_no) == None or btoc[box_no] > cost:
                btoc[box_no] = cost
                btok[box_no] = k+1

    if len(btoc) < N:
        print(-1)
    else:
        print(sum({ktoc[btok[str(b)]] for b in range(1, N+1)}))
        
        

main()