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:
from collections import defaultdict

INF = float('inf')
N, M = map(int, input().split())
A = defaultdict(lambda: -1)
C = [[] for _ in range(M)]
treasure_cost = [INF] * N
for i in range(M):
    a, _ = map(int, input().split())
    *temp, = map(int, input().split())
    A[a] = i if A[a] == -1 or len(temp) > len(C[A[a]]) else A[a]
    C[i] += temp
    for t in temp:
        treasure_cost[t-1] = min(treasure_cost[t-1], a)
ans = 0
for i in range(N):
    a = treasure_cost[i]
    if a == INF: print(-1); break
    elif a == -1: continue
    ans += treasure_cost[i]
    for c in C[A[a]]:
        treasure_cost[c-1] = -1
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, M = map(int, input().split())
    a = [None]*M
    b = [None]*M
    c = [None]*M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        c[i] = [int(i) for i in input().split()]


    c_list = [None] * N
    inf = 10**6
    minlist = [inf] * N
    for i in range(N):
        for j in range(M):
            if i+1 in c[j]:
                if a[j] < minlist[i]:
                    minlist[i] = a[j]
                    c_list[i] = j
    
    if inf in minlist:
        print("-1")
    else:
        ans = 10**7
        #print(c_list)
        for i in range(2**N):
            key = set()
            sum_tmp = 0
            for j in range(N):
                if ((i >> j) & 1):
                    key |= set(c[c_list[j]])
                    sum_tmp += a[c_list[j]]
            if len(key) == N:
                ans = min(ans, sum_tmp)
        
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, M = map(int, input().split())
    a = [None]*M
    b = [None]*M
    c = [None]*M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        c[i] = [int(i) for i in input().split()]


    flag = [False] * N
    c_list = [None] * N
    inf = 10**5 + 10
    minlist = [inf] * N
    for i in range(N):
        for j in range(M):
            if i+1 in c[j]:
                if a[j] < minlist[i]:
                    minlist[i] = a[j]
                    c_list[i] = j
    
    if inf in minlist:
        print("-1")
    else:
        ans = 10**7
        #print(c_list)
        for i in range(2**N):
            key = set()
            sum_tmp = 0
            for j in range(N):
                if ((i >> j) & 1):
                    key |= set(c[c_list[j]])
                    sum_tmp += a[c_list[j]]
                if len(key) == N:
                    ans = min(ans, sum_tmp)
        
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
keys = [[10**5+1, (0,)] for i in range(M)]
treasures = [0 for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    match = tuple(map(int, input().split()))
    keys[i][0]=a
    keys[i][1]=match
keys.sort(key=lambda x: x[0])
for i in range(M):
    matches = keys[i][1]
    sumVal = sum(list(map(lambda x: keys[x-1][0], set(treasures)))) + treasures.count(0)*(10**5)
    tmpTreasures = treasures[::]
    for j in matches:
        tmpTreasures[j-1] = i+1
    tmpSumVal = sum(list(map(lambda x: keys[x-1][0], set(tmpTreasures)))) + tmpTreasures.count(0)*(10**5)
    if tmpSumVal < sumVal:
        treasures = tmpTreasures

ans = sum(list(map(lambda x: keys[x-1][0], set(treasures)))) if treasures.count(0) == 0 else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
full = 2**N
dp = [float("inf")]*full
dp[0] = 0

for m in range(M):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))
    num = 0
    for c in C:
        num += 2**(c-1)
    for i in range(full):
        if dp[i]!=float("inf"):
            dp[i|num] = min(dp[i|num],dp[i]+a)
print(dp[-1])

Submission status: Wrong Answer

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

inf = 10 ** 10

dp = [inf] * (1 << N)
dp[0] = 0
print(dp)


for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])
    #print(a, b)
    #print(c)

    for j in range(1 << N):
      dp[j | c] = min(dp[j] + a, dp[j | c])
      # print(j | c)
res = dp[-1] if dp[-1] != inf else -1
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_list = np.zeros(m+1).astype(int)
c_list = np.zeros(m+1).astype(int)

for i in range(1,m+1):
    a_list[i],b = map(int,input().split())
    c_s = list(map(int, input().split()))
    c_2 = 0
    for c in c_s:
        c_2 += 2**(c)
    c_list[i] = c_2

dp_list = np.full([n+1,m+1], 10**8).astype(int)
bit_list = np.zeros([n+1,m+1]).astype(int)
dp_list[0] = 0

for i in range(1,n+1):
    non_i_cost,non_i_bit = dp_list[i-1,0], bit_list[0,0]
    have_i_cost,have_i_bit = -1, bit_list[0,0]

    for j in range(1,m+1):
        before_cost,before_bit = dp_list[i-1,j] , bit_list[i-1,j]

        if(bin((before_bit >> i) & 1) == bin(1)):
            if(before_cost <= have_i_cost)|(have_i_cost == -1):
                have_i_cost,have_i_bit = before_cost,before_bit
        else:
            if(before_cost <= non_i_cost):
                non_i_cost,non_i_bit = before_cost ,before_bit

        c = c_list[j]
        if (bin((c >> i) & 1) == bin(1)) :
            if (non_i_cost + a_list[j] <= min(dp_list[i,j-1], (have_i_cost if have_i_cost != -1 else 10**9))):
                dp_list[i,j] = non_i_cost + a_list[j]
                bit_list[i,j] = non_i_bit | c_list[j]
            elif(dp_list[i,j-1] >= have_i_cost)&(have_i_cost != -1):
                dp_list[i,j], bit_list[i,j] = have_i_cost ,have_i_bit
            else:
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]


            # if ( dp_list[i,j-1] < non_i_cost + a_list[j]):
            #     dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            # else:
            #     dp_list[i,j] = non_i_cost + a_list[j]
            #     bit_list[i,j] = non_i_bit | c_list[j]
        else:
            if ( dp_list[i,j-1] < have_i_cost)|(have_i_cost == -1):
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            else:
                dp_list[i,j], bit_list[i,j] = have_i_cost ,have_i_bit


if(dp_list[n,m] >= 10**8):
    print(-1)
else:
    print(dp_list[n,m])

# print(dp_list)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_list = np.zeros(m+1).astype(int)
c_list = np.zeros(m+1).astype(int)

for i in range(1,m+1):
    a_list[i],b = map(int,input().split())
    c_s = list(map(int, input().split()))
    c_2 = 0
    for c in c_s:
        c_2 += 2**(c)
    c_list[i] = c_2

dp_list = np.full([n+1,m+1], 10**8).astype(int)
bit_list = np.zeros([n+1,m+1]).astype(int)
dp_list[0] = 0

for i in range(1,n+1):
    non_i_cost,non_i_bit = dp_list[i-1,0], bit_list[0,0]
    have_i_cost,have_i_bit = -1, bit_list[0,0]

    for j in range(1,m+1):
        before_cost,before_bit = dp_list[i-1,j] , bit_list[i-1,j]

        if(bin((before_bit >> i) & 1) == bin(1)):
            if(before_cost <= have_i_cost)|(have_i_cost == -1):
                have_i_cost,have_i_bit = before_cost,before_bit
        else:
            if(before_cost <= non_i_cost):
                non_i_cost,non_i_bit = before_cost ,before_bit

        c = c_list[j]
        if (bin((c >> i) & 1) == bin(1)) :
            if (non_i_cost + a_list[j] <= min(dp_list[i,j-1], (have_i_cost if have_i_cost != -1 else 10**8))):
                dp_list[i,j] = non_i_cost + a_list[j]
                bit_list[i,j] = non_i_bit | c_list[j]
            elif(dp_list[i,j-1] >= have_i_cost)&(have_i_cost != -1):
                dp_list[i,j], bit_list[i,j] = have_i_cost ,have_i_bit
            else:
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]


            # if ( dp_list[i,j-1] < non_i_cost + a_list[j]):
            #     dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            # else:
            #     dp_list[i,j] = non_i_cost + a_list[j]
            #     bit_list[i,j] = non_i_bit | c_list[j]
        else:
            if ( dp_list[i,j-1] < have_i_cost)|(have_i_cost == -1):
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            else:
                dp_list[i,j], bit_list[i,j] = have_i_cost ,have_i_bit


if(dp_list[n,m] >= 10**8):
    print(-1)
else:
    print(dp_list[n,m])

# print(dp_list)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_list = np.zeros(m+1).astype(int)
c_list = np.zeros(m+1).astype(int)

for i in range(1,m+1):
    a_list[i],b = map(int,input().split())
    c_s = list(map(int, input().split()))
    c_2 = 0
    for c in c_s:
        c_2 += 2**(c)
    c_list[i] = c_2

dp_list = np.full([n+1,m+1], 10**8).astype(int)
bit_list = np.zeros([n+1,m+1]).astype(int)
dp_list[0] = 0

for i in range(1,n+1):
    non_i_cost,non_i_bit = dp_list[i-1,0], bit_list[0,0]
    have_i_cost,have_i_bit = -1, bit_list[0,0]

    for j in range(1,m+1):
        before_cost,before_bit = dp_list[i-1,j] , bit_list[i-1,j]

        if(bin((before_bit >> i) & 1) == bin(1)):
            if(before_cost <= have_i_cost)|(have_i_cost == -1):
                have_i_cost,have_i_bit = before_cost,before_bit
        else:
            if(before_cost <= non_i_cost):
                non_i_cost,non_i_bit = before_cost ,before_bit

        c = c_list[j]
        if (bin((c >> i) & 1) == bin(1)) :
            if ( dp_list[i,j-1] < non_i_cost + a_list[j]):
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            else:
                dp_list[i,j] = non_i_cost + a_list[j]
                bit_list[i,j] = non_i_bit | c_list[j]
        else:
            if ( dp_list[i,j-1] < have_i_cost)|(have_i_cost == -1):
                dp_list[i,j], bit_list[i,j] = dp_list[i,j-1], bit_list[i,j-1]
            else:
                dp_list[i,j], bit_list[i,j] = have_i_cost ,have_i_bit


if(dp_list[n,m] >= 10**8):
    print(-1)
else:
    print(dp_list[n,m])

Submission status: Wrong Answer

Solution code:
import numpy as np

l = map(int, raw_input().split())
N = l[0]
M = l[1]

costs = []
keys = []

for i in range(M):
    l = map(int, raw_input().split())
    costs.append(l[0])

    cin = map(int, raw_input().split())
    key = 0
    for c in cin:
        key = key  | 1 << c-1
    keys.append(key)

dp = np.full((1 << N, M), np.inf)

# j = 0                                                                                                
key = keys[0]
new_state = 0 | key
dp[new_state][0] = costs[0]

for j in range(1,M):
    key = keys[j]
    for i in range(1 << N):
        new_state = i | key
        dp[new_state][j] = min(dp[new_state][j-1], dp[i][j-1] + costs[j], dp[new_state][j])

ans = dp[-1][-1]
if ans == np.inf:
    print "-1"
else:
    print int(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
keys=[None]*m
dp=[-1]*(2**n)
for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cond=0
  for j in c:
    cond+=2**(j-1)
  keys[i]=[a,cond]
for key in keys:
  for sta in range(2**n):
    if dp[sta|key[1]]==-1:
      dp[sta|key[1]]=key[0]
    else:
      dp[sta|key[1]]=min(dp[sta|key[1]],dp[sta]+key[0])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [0] * m
    c = [0] * m

    for i in range(m):
        ai, bi = [int(s) for s in sys.stdin.readline().strip().split()]
        a[i] = ai
        ci = [int(s)-1 for s in sys.stdin.readline().strip().split()]
        c_val = sum([2 ** num for num in ci])
        c[i] = c_val

    dp = [[float('inf')] * (n ** 2) for _ in range(m)]
    for i in range(m):
        dp[i][0] = 0

    for j in range(n**2):
        first_key_boxes = c[0]
        if first_key_boxes & j == j:
            dp[0][j] = a[0]

    for i in range(1, m):
        for j in range(1, n ** 2):
            prev = j & (~c[i])
            dp[i][j] = min(dp[i-1][j], a[i] + dp[i-1][prev])
    if dp[m-1][n**2-1] == float('inf'):
        print(-1)
    else:
        print(dp[m-1][n**2-1])


main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [0] * m
    c = [0] * m

    for i in range(m):
        ai, bi = [int(s) for s in sys.stdin.readline().strip().split()]
        a[i] = ai
        ci = [int(s)-1 for s in sys.stdin.readline().strip().split()]
        c_val = sum([2 ** num for num in ci])
        c[i] = c_val

    dp = [[float('inf')] * (n ** 2) for _ in range(m)]
    for i in range(m):
        dp[i][0] = 0

    for j in range(n**2):
        first_key_boxes = c[0]
        if first_key_boxes & j == j:
            dp[0][j] = a[0]

    for i in range(1, m):
        for j in range(n ** 2):
            prev = j & (~c[i])
            dp[i][j] = min(dp[i-1][j], a[i] + dp[i-1][prev])
    if dp[m-1][n**2-1] == float('inf'):
        print(-1)
    else:
        print(dp[m-1][n**2-1])


main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [0] * m
    c = [0] * m

    for i in range(m):
        ai, bi = [int(s) for s in sys.stdin.readline().strip().split()]
        a[i] = ai
        ci = [int(s)-1 for s in sys.stdin.readline().strip().split()]
        c_val = sum([2 ** num for num in ci])
        c[i] = c_val

    dp = [[float('inf')] * (n ** 2) for _ in range(m)]
    for i in range(m):
        dp[i][0] = 0

    for j in range(n**2):
        first_key_boxes = c[0]
        if first_key_boxes & j == j:
            dp[0][j] = a[0]

    for i in range(1, m):
        for j in range(n ** 2):
            for k in range(n):
                prev = j & (~c[i])
            dp[i][j] = min(dp[i-1][j], a[i] + dp[i-1][prev])
    if dp[m-1][n**2-1] == float('inf'):
        print(-1)
    else:
        print(dp[m-1][n**2-1])


main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L={}
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for j in c:
        d+=2**(N-j)
    L[d]=a
#print(L)

D={}
D[0]=0
C=0
for i in range(N):
    C+=2**(N-1-i)
    E={}
    for j in D:
        for k in L:
            if j>=C:
                if j not in E:
                    E[j]=D[j]
                else:
                    if E[j]>D[j]:
                        E[j]=D[j]
            if j|k>=C:
                if j|k not in E:
                    E[j|k]=D[j]+L[k]
                else:
                    if E[j|k]>D[j]+L[k]:
                        E[j|k]=D[j]+L[k]
    #print(E)
    D=E
if len(D)==0:
    print(-1)
else:
    print(D[2**N-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

l = map(int, raw_input().split())
N = l[0]
M = l[1]

costs = []
keys = []

for i in range(M):
    l = map(int, raw_input().split())
    costs.append(l[0])

    cin = map(int, raw_input().split())
    key = 0
    for c in cin:
        key = key  | 1 << c-1
    keys.append(key)

dp = np.full((1 << N, M), np.inf)

# j = 0                                                                                                
key = keys[0]
new_state = 0 | key
dp[new_state][0] = costs[0]


for j in range(1,M):
    key = keys[j]
    for i in range(1 << N):
        min_temp = np.inf
        for k in range(1 <<N):
            new_state = k | key
            if new_state == i:
                min_temp = min(min_temp, dp[k,j-1])
        dp[i][j] = min(dp[i][j-1], min_temp+costs[j])


ans = dp[-1][-1]
if ans == np.inf:
    print "-1"
else:
    print int(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

l = map(int, raw_input().split())
N = l[0]
M = l[1]

costs = []
keys = []

for i in range(M):
    l = map(int, raw_input().split())
    costs.append(l[0])

    cin = map(int, raw_input().split())
    key = 0
    for c in cin:
        key = key  | 1 << c-1
    keys.append(key)

dp = np.full((1 << N, M), np.inf)

# j = 0                                                                                                
key = keys[0]
new_state = 0 | key
dp[new_state][0] = costs[0]


for j in range(1,M):
    key = keys[j]
    for i in range(1 << N):
        min_temp = np.inf
        for k in range(1 <<N):
            new_state = k | key
            if new_state == i:
                min_temp = min(min_temp, dp[k,j-1])
        dp[i][j] = min(dp[i][j-1], min_temp+costs[j])


ans = dp[-1][-1]
if ans == np.inf:
    print "-1"
else:
    print ans

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
N = list(range(1,n+1))
a,b=[],[]
c =[0]*m
for i in range(m):
    ai,bi =  list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
    c[i] = list(map(int,input().split()))

ans_idx = []
impossible = False
while len(N) > 0:
    n = N.pop(0)
    c_idx = []
    for i in range(m):
        if c[i][0] == n:
            c_idx.append(i)
    if c_idx == []:
        impossible = True
        break
    a_val = []
    for i in range(len(c_idx)):
        a_val.append(a[c_idx[i]])
    min_idx = a_val.index(min(a_val))
    ans_idx.append(c_idx[min_idx])
    for i in range(len(c[c_idx[min_idx]])):
        if c[c_idx[min_idx]][i] in N:
            N.remove(c[c_idx[min_idx]][i])
    for i in range(len(c_idx)):
        if len(c[c_idx[i]]) > 1:
            c[c_idx[i]].remove(n)
#print(ans_idx)    
ans = 0
for i in range(len(ans_idx)):
    ans = ans + a[ans_idx[i]]
if impossible == True:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
N = list(range(1,n+1))
a,b=[],[]
c =[0]*m
for i in range(m):
    ai,bi =  list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
    c[i] = list(map(int,input().split()))

ans_idx = []
impossible = False
while len(N) > 0:
    n = N.pop(0)
    c_idx = []
    for i in range(m):
        if c[i][0] == n:
            c_idx.append(i)
    if c_idx == []:
        impossible = True
        break
    a_val = []
    for i in range(len(c_idx)):
        a_val.append(a[c_idx[i]])
    min_idx = a_val.index(min(a_val))
    ans_idx.append(c_idx[min_idx])
    for i in range(len(c[c_idx[min_idx]])):
        if c[c_idx[min_idx]][i] in N:
            N.remove(c[c_idx[min_idx]][i])    
ans = 0
for i in range(len(ans_idx)):
    ans = ans + a[ans_idx[i]]
if impossible == True:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
from collections import defaultdict
from itertools import combinations

d = defaultdict(lambda :-1)
dp = defaultdict(lambda : -1)

for i in range(M):
    a,b = map(int,input().split())
    c = tuple(set(map(int,input().split())))
    if d[c]==-1:
        d[c]=a
    else:
        d[c]=min(a,d[c])
d[tuple()] = 0

for i in range(0,N):
    for p in combinations(range(1,N+1),N-i):
        if d[p]!=-1:
            for j in range(1,N-i):
                for q in combinations(p,j):
                    if d[q]==-1:
                        d[q]=d[p]
                    else:
                        d[q]=min(d[p],d[q])

for i in range(1,N+1):
    for p in combinations(range(1,N+1),i):
        for j in range(0,i+1):
            for q in combinations(p,j):
                r = tuple(set(p)-set(q))
                if d[q]!=-1 and d[r]!=-1:
                    if d[p]==-1:
                        d[p] = d[q] + d[r]
                    else:
                        d[p] = min(d[p],d[q]+d[r])

print(d[tuple(range(1,N+1))])

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
dp_1 = [float("inf") for i in range(2**n)]
dp_2 = [float("inf") for i in range(2**n)]
dp_1[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        if j % 2 == 0:
            dp_2[j|c] = min(dp_1[j|c], dp_1[j] + a, dp_2[j|c])
            dp_2[j] = min(dp_1[j], dp_2[j])
        else:
            dp_1[j|c] = min(dp_2[j|c], dp_2[j] + a, dp_1[j|c])
            dp_1[j] = min(dp_2[j], dp_1[j])

print([dp_1[-1], -1][dp_1[-1] == float("inf")])

Submission status: Wrong Answer

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

inf = 1e9+7
dp = [inf] * (1 << N)

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

    hako = list(map(int, input().split()))

    mask = sum(1 << (c-1) for c in hako)

    for i in range(1 << N):
        dp[i | mask] = min(dp[i | mask], dp[i] + a)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = list(map(int, input().split(" ")))
dp = [np.inf] * (1 << N)
dp[0] = 0
bits = set()
bits.add(0)

for i in range(M):
    val,b = list(map(int, input().split(" ")))
    opens = list(map(int, input().split(" ")))
        
    # OpensからBitへの変換
    keybits = 0
    for tmp in opens:
        keybits += 1 << tmp-1
    
    for prev in list(bits):
        target = prev | keybits
        dp[target] = min(dp[target], dp[prev]+val)
        bits.add(target)
    
print(dp[-1])

Submission status: Wrong Answer

Solution code:

N,M = map(int, input().split())
A = []
comp = sum(10**(x-1) for x in range(1,N+1))
for m in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  box = sum(10**(x-1) for x in c)
  A.append([box, a])

  for i in range(0,len(A)-1):
    A.append([A[0|i][0] + A[m][0], 
              A[0|i][1] + A[m][1]])

if max([A[x][1] for x in range(len(A))]) >= comp:
    ans = min([A[x][1] for x in range(len(A))
           if A[x][0] >= comp] )
else:
       ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
dp = [float("inf") for i in range(2**n)]

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])
    for j in range(n**2):
        if j == 0:
            dp[c] = min(dp[c], a)

        elif dp[j] != float("inf"):
            dp[j|c] = min(dp[j|c], dp[j] + a)

print([dp[-1], -1][dp[-1] == float("inf")])

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
dp = [float("inf") for i in range(2**n)]

for i in range(m):
    a, _ = [int(i) for i in input().split()]
    c = sum([2**(int(i)-1) for i in input().split()])
    for j in range(n**2):
        if j == 0:
            dp[c] = min(dp[c], a)

        elif dp[j] != float("inf"):
            dp[j|c] = min(dp[j|c], dp[j] + a)

print([dp[-1], -1][dp[-1] == float("inf")])

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n,m = map(int,input().split())
boxes = [[]for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    cs = list(map(lambda x: int(x)-1,input().split()))
    c = [0 for _ in range(n)]
    for i in cs:
        c[i]=1
    boxes[cs[0]].append((c,a))
'''        
if not all([x for x in boxes]):
    print(-1)
    exit()
''' 
union ={tuple([0 for _ in range(n)]):0}
for i,box in enumerate(boxes):
    union2 ={}
    for c2,a2 in union.items():
        if c2[i]:
            union2[c2]=a2
    for c1,a1 in box:
        for c2,a2 in union.items():
            c3 = tuple(np.logical_or(c1, c2))
            a3 = a1 + a2
            if not c3 in union2:
                union2[c3] = a3
            elif a3 < union2[c3]:
                union2[c3] = a3
    union = union2
alltrue = tuple([True for _ in range(n)])
if alltrue in union:
    print(union[alltrue])
else:
    print(-1)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for cc in c:
        C[i] += (1<<(cc-1)) # bit

dp = [[MAX]*(2**N) for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
#    for p in range(M):
#        print(dp[p])
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j]+ab[i][0])

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
dp = [float("inf")]*(2**n)
dp[0] = 0
for M in range(m):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))

    state = 0
    for c in C:
        state += 2**(c-1)

    for i in range(2**n):
        if dp[i|state] != float("inf"):
            dp[i|state] = min(dp[i]+a,dp[i|state])
        # else:
        #     dp[i|state] = dp[i]+a

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce
import math

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

for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    c.append([int(x) for x in input().split()])
#print(a, b, c)


if len(reduce(lambda x, y: list(set(x)|set(y)), c))<n:
    print(-1)
    sys.exit()

costs = []

def f(boxnum, keyidx, canopen, cost):
    if len(canopen)==n:
        return canopen, cost
    
    if boxnum == n:
        pass
    else:
        canopen, cost = f(boxnum+1, keyidx+1, canopen, cost)
        
    thiscost = 100000
    for keyidx in range(keyidx, m+1):
        if boxnum not in canopen and boxnum in c[keyidx-1] and a[keyidx-1]<=thiscost:
            canopen = canopen|set(c[keyidx-1])
            thiscost = a[keyidx-1]
    if thiscost==100000:
        thiscost=0
        
    cost = cost + thiscost
    
    #print(canopen, cost)
    if len(canopen)==n:
        #print(canopen, cost)
        costs.append(cost)
    return canopen, cost


for j in range(1, m+1):
    for i in range(1, n+1):
        canopen, cost = f(i, j, set(), 0)

print(min(costs))

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 = 2**8 - 1
dp = [[inf]*(2**N+1) for _ in range(M+1)]
dp[0][0] = 0

c_bit = [0] * M
for i in range(M):
    for t in c[i]:
        c_bit[i] += 1<<(t-1)

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|c_bit[i]] = min(dp[i+1][j|c_bit[i]],dp[i][j]+a[i])
        

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

Submission status: Wrong Answer

Solution code:
import collections
N,M=map(int,input().split())
L=[]
for i in range(M):
  a,b=map(int,input().split())
  l=[]
  l.append(a)
  l.append(b)
  l.append(list(map(int,input().split())))
  l.append(a/b)
  L.append(l)
  
L.sort(key=lambda x:x[3])

op=[]
ans=0

for k in range(M):
  L.sort(key=lambda x:x[3])
  if L[0][1]!=0:
    ans+=L[0][0]
  for i in L[0][2]:
    op.append(i)
    for j in L:
      if i in j[2]:
        j[1]-=1
    if j[1]!=0:
      j[3]=j[0]/j[1]
  L.pop(0)
  print(L,ans,op)
  
c=collections.Counter(op).keys()
if len(c)<N:
  print(-1)
else:
  print(ans)

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:
        use_keys = {btok[str(b)] for b in range(1, N+1)} 
        print(sum([ktoc[k] for k in use_keys]))

main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

MOD = 10**9+7
INF = float('inf')

"""
## test data 
# input
5 5
10 2
1 3
15 2
2 4
5 2
3 5
20 1
5
20 4
1 2 3 4

# output
25
"""

def main():
    N,M=[int(x) for x in input().split()]
    dp = [INF] * 2**N
    dp[0]=0
    for i in range(M):
        a,b=[int(x) for x in input().split()]
        c=sum([1 << (p-1) for p in list(map(int, input().split()))])
        for j in range(2**N):
            dp[j|c]=min(dp[j|c], dp[j]+a)
    print(dp[-1])

main()