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 numpy as np

N, M = map(int, input().split())  # N個の宝箱, M個の鍵

keys = [None]*M
# 宝箱は1-N個
for i in range(M):
    a, b = map(int, input().split())  # 鍵のコスト, 開けれる宝箱の種類の数
    c_list = list(map(int, input().split()))  # 開けれる宝箱の種類
    s = 0  # 集合s
    for c in c_list:
        c -= 1  # idx 0 スタートにする
        s = s | 1<<c
    keys[i] = (s, a)  # (鍵を使って推移開けれる宝箱の集合, 鍵のコスト)

# dp = np.ones(1<<N) * np.inf  # N個の宝箱の状態を表す集合のパターンは 2^N 個ある
INF = 1e12
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())  # N個の宝箱, M個の鍵

keys = [None]*M
# 宝箱は1-N個
for i in range(M):
    a, b = map(int, input().split())  # 鍵のコスト, 開けれる宝箱の種類の数
    c_list = list(map(int, input().split()))  # 開けれる宝箱の種類
    s = 0  # 集合s
    for c in c_list:
        c -= 1  # idx 0 スタートにする
        s = s | 1<<c
    keys[i] = (s, a)  # (鍵を使って推移開けれる宝箱の集合, 鍵のコスト)

dp = np.ones(1<<N) * np.inf  # N個の宝箱の状態を表す集合のパターンは 2^N 個ある
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())  # N個の宝箱, M個の鍵

keys = [None for _ in range(M)]
# 宝箱は1-N個
for i in range(M):
    a, b = map(int, input().split())  # 鍵のコスト, 開けれる宝箱の種類の数
    c_list = list(map(int, input().split()))  # 開けれる宝箱の種類
    s = 0  # 集合s
    for c in c_list:
        c -= 1  # idx 0 スタートにする
        s = s | 1<<c
    keys[i] = (s, a)  # (鍵を使って推移開けれる宝箱の集合, 鍵のコスト)

dp = np.ones(1<<N) * np.inf  # N個の宝箱の状態を表す集合のパターンは 2^N 個ある
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | keys[i][0]
        cost = dp[s] + keys[i][1]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

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

dp = [10**6 for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

if dp[2**n-1] != 10**6:
    print(dp[2**n-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = [np.inf for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

if dp[2**n-1] != np.inf:
    print(dp[2**n-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = [[np.inf for i in range(2**n)] for j in range(m)]
for i in range(m):
    dp[i][0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[0][num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[i][j|di] = min(dp[i][j|di], dp[i-1][j|di], dp[i-1][j]+a[i])
    for j in range(2**n):
        if dp[i][j] == np.inf and dp[i-1][j] != np.inf:
            dp[i][j] = dp[i-1][j]

if dp[m-1][2**n-1] != np.inf:
    print(dp[m-1][2**n-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

N, M = map(int, sys.stdin.readline().split())
memo = defaultdict(lambda: defaultdict(lambda: int(-1)))
key_treasure = [0]*M
cost = [0]*M
total = 0

for i in range(N):
	total |= 1 << i
for i in range(M):
	key_cost, q = map(int, sys.stdin.readline().split())
	cost[i] = key_cost

	treasure = list(map(int, sys.stdin.readline().split()))
	for j in range(q):
		key_treasure[i] |= 1 << (treasure[j] - 1)

def dp(key, treasures):
	if key == M:
		if treasures == total: return 0
		else: return float('inf')
	if memo[key][treasures] != -1: return memo[key][treasures]

	incl = dp(key+1, treasures | key_treasure[key]) + cost[key]
	excl = dp(key+1, treasures)
	ans = memo[key][treasures] = min(incl, excl)
	return ans

ans = dp(0, 0)
print(-1 if ans== float('inf') else ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  C=[int(i) for i in input().split()]
  x=0
  for c in C:
    x|=(1<<(c-1))
  A.append((a,x))
DP=[float("inf")]*(2**n)
DP[0]=0
for i in range(m):
  a,x=A[i]
  for j in range(2**n):

    DP[j|x]=min(DP[j|x],DP[j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))
    value.append([A, c])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        dp[t] = min(dp[t], cost)
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    binary = 0
    for c in C:
        binary |= 1<<(c-1)
    value.append([A, binary])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        dp[t] = min(dp[t], cost)
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    binary = 0
    for c in C:
        binary += 1<<(c-1)
    value.append([A, binary])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        dp[t] = min(dp[t], cost)
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    binary = 0
    for c in C:
        binary += 1<<(c-1)
    value.append([A, binary])
    
dp = [float("inf") for _ in range(1<<n)]
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        dp[t] = min(dp[t], cost)
if dp[(1<<n)-1] == float("inf"):
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
value = []
weight = []
for i in range(m):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    binary = 0
    for c in C:
        binary += 2**(c-1)
    value.append(A)
    weight.append(binary)
    
dp = [float("inf") for _ in range(2**n)]
dp[0] = 0
for s in range(2**n):
    for i in range(m):
        t = s | weight[i]
        cost = dp[s] + value[i]
        dp[t] = min(dp[t], cost)
if dp[2**n-1] == float("inf"):
    print(-1)
else:
    print(dp[2**n-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
value = []
weight = []
for i in range(m):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    binary = 0
    for c in C:
        binary += 2**(c-1)
    value.append(A)
    weight.append(binary)
    
dp = [float("inf") for _ in range(2**n)]
dp[0] = 0
for s in range(2**n):
    for i in range(m):
        t = s | weight[i]
        cost = dp[s] + value[i]
        dp[t] = min(dp[t], cost)
if dp[2**n-1] == float("inf"):
    print(-1)
else:
    print(dp[2**n-1])

Submission status: Time Limit Exceeded

Solution code:
#解説放送見てからの書き直し
import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  #鍵の金額
    B[i] = b  #開けられる宝箱の種類数
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
dp = [INF]*(1<<N) #2^N
dp[0] = 0
for s in range(1<<N):
    for j in range(M):
        t = s | C[j]
        cost = dp[s] + A[j]
        dp[t] = min(dp[t],cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

N, M = list(map(int, input().split()))
a_list = []
c_list = []
for i in range(M):
    a, _ = list(map(int, input().split()))
    a_list.append(a)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

dp = [INF]*(1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = c_list[i] | s
        cost = a_list[i]+dp[s]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

Solution code:
def calc(N, M, a, c):
    inf = 10 ** 7 + 1
    L = 2 ** N
    dp = [inf for _ in range(L)]
    dp[0] = 0
    C = [sum([_c[i] * 2 ** i for i in range(N)]) for _c in c]
    for _ in range(M):
        dp_x = list(dp)
        for i in range(M):
            for j in range(L):
                if dp[j] == inf:
                    continue
                dp_x[j | C[i]] = min(dp_x[j | C[i]], dp[j] + a[i])
            dp = dp_x
        if dp[L - 1] < inf:
            return dp[L - 1]
    return -1


(N, M) = tuple([int(s) for s in input().split(' ')])
a = [0 for _ in range(M)]
c = [[0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    (_a, _b) = tuple([int(s) for s in input().split(' ')])
    a[i] = _a
    for _c in [int(s) for s in input().split(' ')]:
        c[i][_c - 1] = 1
print(calc(N, M, a, c))

Submission status: Time Limit Exceeded

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

a_list = []
c_list = []
for i in range(M):
    a, _ = list(map(int, input().split()))
    a_list.append(a)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

INF = 1001001001


dp = [INF]*(1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = c_list[i] | s
        cost = a_list[i]+dp[s]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
inf=10**12

ab=[]
cs=[]
for i in range(m):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    ab.append((a,b))
    cs.append(c)
dp=[inf]*(2**n)
dp[0]=0
for i in range(m):
    x=0
    for h in cs[i]:
        x+=2**(h-1)
    for j in range(2**n):
        dp[j|x]=min(dp[j|x],dp[j]+ab[i][0])
print(dp[-1] if dp[-1]!=inf else -1)

Submission status: Time Limit Exceeded

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

a_list = []
b_list = []
c_list = []
for i in range(M):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

INF = 1001001001

import numpy as np
dp = np.zeros(1<<N)+INF
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = c_list[i] | s
        cost = a_list[i]+dp[s]
        dp[t] = min(dp[t], cost)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    dp = [[float("inf"), set([])]  for _ in range(2 ** m)]
    dp[0][0] = 0
    a_list = []
    c_list = []
    for i in range(m):
        a, b = map(int, input().split())
        a_list.append(a)
        c_list.append([int(i) for i in input().split()])

    for i in range(1, 2 ** m):
        for j in range(m):
            c = c_list[j]
            a = a_list[j]
            if (i & (1 << j) == 1 << j):
                if len(set(c) - dp[i - (1 << j)][1]) > 0:
                    if len(set(c) - dp[i][1]) > 0:
                        dp[i][0] = dp[i - (1 << j)][0] + a
                        dp[i][1] = dp[i - (1 << j)][1] | set(c)
                    else:
                        if dp[i][0] > dp[i - (1 << j)][0] + a:
                            dp[i][0] = dp[i - (1 << j)][0] + a
                        else:
                            continue
                elif len(dp[i - (1 << j)][1]) == n:
                    if len(dp[i][1]) == n:                    
                        dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0])
                    elif len(set(c) | dp[i][1]) == n:
                        dp[i][1] = dp[i - (1 << j)][1] | set(c)
                        dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0] + a)
    if len(dp[-1][1]) == n:
        print(dp[-1][0])
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [[float("inf"), set([])]  for _ in range(2 ** m)]
dp[0][0] = 0
a_list = []
c_list = []
for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    c_list.append([int(i) for i in input().split()])

for i in range(1, 2 ** m):
    for j in range(m):
        c = c_list[j]
        a = a_list[j]
        if (i & (1 << j) == 1 << j):
            if len(set(c) - dp[i - (1 << j)][1]) > 0:
                if len(set(c) - dp[i][1]) > 0:
                    dp[i][0] = dp[i - (1 << j)][0] + a
                    dp[i][1] = dp[i - (1 << j)][1] | set(c)
                else:
                    if dp[i][0] > dp[i - (1 << j)][0] + a:
                        dp[i][0] = dp[i - (1 << j)][0] + a
                    else:
                        continue
            elif len(dp[i - (1 << j)][1]) == n:
                if len(dp[i][1]) == n:                    
                    dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0])
                elif len(set(c) | dp[i][1]) == n:
                    dp[i][1] = dp[i - (1 << j)][1] | set(c)
                    dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0] + a)
if len(dp[-1][1]) == n:
    print(dp[-1][0])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
A = []
C = []

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))

import numpy as np


inf = 1000000000
dp = np.zeros(2**N).astype('int')

dp[:] = inf
dp[0] = 0


for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost


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

Submission status: Time Limit Exceeded

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

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))

import numpy as np


inf = 1000000000
dp = np.zeros(2**N).astype('int')

dp[:] = inf
dp[0] = 0


for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost


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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp_i=[set([j for j in range(M)]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( dp_i[i])
        min_key=0
        true_new_i=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            if dp[new_i] > cost:
                dp[new_i] = cost 
                min_key = j
                true_new_i=new_i
                
        dp_i[true_new_i] = dp_i[i] - set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp_i=[set([j for j in range(M)]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( dp_i[i])
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            if dp[new_i] > cost:
                dp[new_i] = cost 
                min_key = j
                
        dp_i[i] = dp_i[i] - set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp_i=[set([j for j in range(M)]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( dp_i[i])
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
            min_key = j
        dp_i[i] = dp_i[i] - set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    sets=set([j for j in range(M)])
    dp_i=[set([]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( sets - set(dp_i[i]))
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
            min_key = j
        dp_i[i] = dp_i[i] | set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 

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

main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の解法

INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        c -= 1
        s |= 1 << c
    key.append((s, a))

dp = [INF] * (1 << N)
dp[0] = 0
for s in range(1 << N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)

ans = dp[-1]
if ans == INF:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    temp = map(lambda x: 1<<(x-1), many_int())
    sums = sum(temp)
    treasures.append(sums)

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index-1):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index-1):
    for j in range(M):
        new_i = int(bin(int(treasures[j],2) | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)
    
    for k in range(max_index):
        new_i = int(bin(treasures[i] | k),2)
        cost = dp[k] + key_list[i]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)

treasures

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

# 全ての部分集合の列挙
def subset_family(items, length):
    subsets = []
    for i in range(length + 1):
        for c in combinations(items, i):
            subsets.append(c)
    return subsets


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

dp = [[float('inf')] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0
"""
dp[i][j] = (i + 1 番目以降の鍵は購入せずに状態を j にする為に必要な最小費用)
部分集合族はビットで管理すれば良い(0 <= j <= 2**N-1)
"""

for i in range(1, M + 1):
    dp[i] = dp[i - 1]
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** N):
        """
        DPは送る方向に考えるか受け取る方向に考えるかの２通りのやり方がある
        今回は受け取る方は難しいので送る方で考える
        またjは昇順に考えると偶然うまくDPの状態が順番に確定していく
        """
        for subset in subset_family(c, b):
            val = 0
            for num in subset:
                val += 2 ** (num - 1)

            if j | val < 2 ** N:
                dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
    #print('dp[{}]={}'.format(i, dp[i]))

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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    sums = 0
    for i in temp:
        sums += 1<<(i-1)
    treasures.append(sums)

treasures

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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

Submission status: Time Limit Exceeded

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    sums = 0
    for i in temp:
        sums = int(bin(sums | 1<<(i-1)),2)
    treasures.append(sums)

treasures

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

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