Problem:


Score : 300 points

Problem

Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0.

Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M).
There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])
c = arr.T[0] # c[n-1]まで
a = arr.T[1:].T # a[n-1][m-1]まで

ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    # 二進数の右から0番目〜n-1番目をみていき、使用or不使用を判断
    for j in range(n):
    # 使用する場合にability/costを更新
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    # 条件クリアしている場合にansを更新
    if np.all(ability>=x): ans = min(ans,cost)

# ansが無限なら、未更新＝条件クリアしてないので-1を出力
ans = -1 if ans==np.inf else ans
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
ans=1e15
for i in range(1<<N):
    B = [0]*M
    C = 0
    for j in range(N):
        if i%2:
            B = [x + y for (x, y) in zip(A[j][1:], B)]
            C += A[j][0]
        i = i//2
    if all(B[i]>=X for i in range(M)):
        ans=min(ans,C)
if ans>=1e15:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:

n,m,x=list(map(int,input().split()))
a=[[] for _ in range(n)]
c=[]
ans =10000000
for i in range(n):
	tmp=input().split()
	c.append(int(tmp[0]))
	a[i]=list(map(int,tmp[1:]))
money_req=[0 for _ in range(1<<n)]
subs_know=[[0 for i in range(m)] for _ in range(1<<n)]	
for  i in range(1<<n):
	for j in range(n):
		if(not((1<<j)&i)):
			money_req[(1<<j)|i]=money_req[i] + c[j]
			flag=0
			for k in range(m):
				subs_know[i|1<<j][k]=subs_know[i][k] + a[j][k]
				if(subs_know[i|1<<j][k]<x): flag=1
			if not flag:ans=min(money_req[1<<j|i],ans);	
if ans==10000000: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])

c = arr.T[0] # c[n-1]まで
a = arr.T[1:].T # a[n-1][m-1]まで


ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    for j in range(n):
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    #print(ability, cost)
    if all(i>=x for i in ability): ans = min(ans,cost)

ans = -1 if ans==np.inf else ans
print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
books = []
cost = []
min_cost = -1
for _ in range(n):
  ca = [int(x) for x in input().split()]
  cost.append(ca[0])
  books.append(ca[1:])
pset = 2**n
for i in range(1,pset):
  indexes = []
  index = 0
  while i!=0:
    if i&1 == 1:
      indexes.append(index)
    index+=1
    i = i//2
  tot_cost = cost[indexes[0]]
  skill = books[indexes[0]].copy()
  for idx in indexes[1:]:
    tot_cost += cost[idx]
    for j in range(m):
      skill[j] += books[idx][j]
  satisfied = True
  for j in range(m):
    if skill[j] < x:
      satisfied = False
      break
  if satisfied:
    if min_cost==-1:
      min_cost = tot_cost
    else:
      min_cost = min(min_cost,tot_cost)
print(min_cost)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = list(map(int,input().split()))
Q = []
C = []
A = []
for i in range(N):
  Q.append(list(map(int,input().split())))
  C.append(Q[i][0])
  A.append(Q[i][1:])
C = np.array(C) #価格行列
A = np.array(A) #スキル行列
           
#全パターンを表す行列Bの作成
B = []
beta = []
for n in range(2**N):
  b = bin(n)[2:].zfill(N)
  beta = []
  for i in range(N):
    beta.append(int(b[i]))
  B.append(beta)
B = np.array(B)

S = np.dot(B,A)
L = []
for n in range(2**N):
  if min(S[n]) >= X:
    L.append(n)
    
if len(L) == 0:
  print(-1)
else:
  kane = []
  for k in range(len(L)):
    kane.append(np.dot(B[L[k]],C))
  print(min(kane))

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
INF=99999999999
ans=INF
for i in range(2**n):
    tans=0
    c=[0]*m
    for j in range(n):
        if (i>>j)&1:
            tans+=a[j][0]
            for k in range(m):
                c[k]+=a[j][k+1]
    
    if min(c)>=x:
        ans=min(tans,ans)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def dfs(i, cost, skills):
    if i == N:
        if min(skills) < X:
            return INF
        else:
            return cost
    new_skills = [a + s for a, s in zip(contents[i], skills)]
    return min(dfs(i + 1, cost, skills), dfs(i + 1, cost + prices[i], new_skills))


INF = float('inf')
N, M, X = map(int, input().split())
prices = []
contents = []
for _ in range(N):
    C, *A = map(int, input().split())
    prices.append(C)
    contents.append(A)
if (ans := dfs(0, 0, [0] * M)) == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
b = [list(map(int, input().split())) for _ in range(n)]
ans = 100000000
for i in range(1<<n):
	res = 0
	s = [0 for _ in range(m)]
	for j in range(n):
		if (i>>j)&1:
			res += b[j][0]
			for k in range(1, m+1):
				s[k-1] += b[j][k]
	if min(s) >= x:
		ans = min(ans, res)
if ans != 100000000:
	print(ans)
else:
	print(-1)

Submission status: Accepted

Solution code:
def dfs(i, cost, skills):
    if i == N:
        if min(skills) < X:
            return INF
        else:
            return cost
    new_skills = [a + s for a, s in zip(contents[i], skills)]
    return min(dfs(i + 1, cost, skills), dfs(i + 1, cost + prices[i], new_skills))


INF = float('inf')
N, M, X = map(int, input().split())
prices = []
contents = []
for _ in range(N):
    C, *A = map(int, input().split())
    prices.append(C)
    contents.append(A)
ans = dfs(0, 0, [0] * M)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

A = [[] for _ in range(n)]
c = [0] * n

for i in range(n):
    c_as = list(map(int, input().split()))
    c[i], A[i] = c_as[0], c_as[1:]

INF = 10**9
ans = INF
    
for s in range(0, 1 << n):
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0:continue
        cost_sum += c[i]
        for j in range(m):
            smart[j] += A[i][j]
    ok = True
    for j in range(m):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]

ans = -1

for i in range(N):
    for choices in itertools.combinations(range(N), i + 1):
        cost = 0
        a = [0] * M
        for choice in choices:
            cost += books[choice][0]
            for j in range(M):
                a[j] += books[choice][j + 1]

        if min(a) >= X:
            ans = min(cost, ans) if ans >= 0 else cost

print(ans)

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
ans = float('inf')

for i in range(2**N):
    c = [0] * M
    a = 0

    idx = 0
    while i:
        if i % 2:
            a += A[idx][0]
            
            for j in range(1, M+1):
                c[j-1] += A[idx][j]
        
        i //= 2
        idx += 1
        
    f = True
    
    for cc in c:
        if cc < X:
            f = False
            break
    if f: ans = min(ans, a)
    
if ans == float('inf'): ans = -1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
for _ in range(n):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
ans = float("inf")
for i in range(2**n):
    res = 0
    D = [0]*m
    for j in range(n):
        if i >> j & 1:
            res += C[j]
            for k, a in enumerate(A[j]):
                D[k] += a
    for d in D:
        if d < x:
            break
    else:
        ans = min(ans, res)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]

ans = -1

for bits in range(1 << N):
    cost = 0
    a = [0] * M
    for i in range(N):
        if (bits >> i) & 1 == 1:
            cost += books[i][0]
            for j in range(M):
                a[j] += books[i][j + 1]

    if min(a) >= X:
        ans = min(cost, ans) if ans >= 0 else cost

print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book = [tuple(map(int, input().split())) for _ in range(N)]

INF = float('inf')


def calc(index, cost, point):
    if index == N:
        if len(list(filter(lambda p: p < X, point))) > 0:
            return INF
        return cost

    np = point[:]
    for i, a in enumerate(book[index][1:]):
        np[i] += a

    return min(calc(index + 1, cost, point), calc(index + 1, cost + book[index][0], np))


res = calc(0, 0, [0 for _ in range(M)])
print(res if res != INF else -1)

Submission status: Accepted

Solution code:
INF=100100100

n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(n):
    t=list(map(int,input().split()))
    c.append(t[0])
    a.append(t[1:])
cost=INF
for i in range(2**n):
    ab=[0]*m
    tmp=0
    for j in range(n):
        idx=i>>j & 1
        if(idx):
            tmp+=c[j]
            for k in range(m):
                ab[k]+=a[j][k]
    for k in range(m):
        if(ab[k]<x):break
    else:cost=min(cost,tmp)
if(INF==cost):print(-1)
else:print(cost)

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
ca_array = []
for i in range(N):
  ca_array.append(list(map(int, input().split())))

resultMoneyArray = []

for c in itertools.product([False, True], repeat=N):
  tmpMoney = 0
  m_array = [X for i in range(M)]
  for j in range(N):
    if c[j]:
      for k in range(M):
        m_array[k] -= ca_array[j][k+1]
      tmpMoney += ca_array[j][0]
      
  if sum(x > 0 for x in m_array) == 0:
    resultMoneyArray.append(tmpMoney)

if len(resultMoneyArray) == 0:
  print(-1)
else:
  print(min(resultMoneyArray))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split()))for _ in range(N)]

    result = []
    for i in range(2**N):
        bins = format(i, "b").zfill(N)
        tmp = [0] * (M + 1)

        for b, ca in zip(bins, CA):
            if b == "1":
                for j in range(M + 1):
                    tmp[j] += ca[j]
        if all([True if k >= X else False for k in tmp[1:]]):
            result.append(tmp)

    if result == []:
        print(-1)
    else:
        print(min([r[0]for r in result]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 再帰で全ての組み合わせを求める
def my_loop(n_counter, my_list):
    if n_counter == N:
        bool_list = [i >= X for i in my_list[1:]]
        if all(bool_list):
            ans.append(my_list[0])
    else:
        # 要素同士を足す
        add_list = [my_list[i] + temp[n_counter][i] for i in range(M+1)]
        my_loop(n_counter+1, my_list)
        my_loop(n_counter+1, add_list)


N, M, X = map(int, input().split())
temp = []
ans = []
for _ in range(N):
    temp.append(list(map(int, input().split())))

my_loop(0, [0]*(M+1))
print(min(ans) if len(ans) != 0 else '-1')

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]
payment=1e10
flag=True
for i in range(2**n):
    total=0
    skil=[0]*m
    for j in range(n):
        if ((i >> j) & 1):
            total+=lis[j][0]
            for h in range(1,m+1):
                skil[h-1]+=lis[j][h]
    for k in skil:
        if k>=x:
            pass
        else:
            break
    else:
        if payment>total:
            payment=total
if payment==1e10:
    print(-1)
else:
    print(payment)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book_list = []
cost = [0] * (2 ** N)

cost_parform = []
for i in range(N):
    book_list.append(list(map(int, input().split())))
for i in range(2 ** N):
    bag = []
    rikaido = [0] * M
    for j in range(N):  # このループが一番のポイント
        if (i >> j & 1):
            bag.append(j)
    for k in bag:
        # print(bag)
        # print(bag[k])
        cost[i] = cost[i] + book_list[k][0]
        for m in range(M):
            rikaido[m] = rikaido[m] + book_list[k][m+1]

    count = 0
    for m in range(M):
        if rikaido[m] >= X:
            count += 1
    if count == M:
        cost_parform.append(cost[i])

if len(cost_parform) == 0:
    x = -1
    print(x)
else:
    print(min(cost_parform))

#print(cost_parform)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]

mn = 10**18
l = [i for i in range(n)]
for cnt in range(1, n+1):
    for v in itertools.combinations(l, cnt):
        cost = 0
        tm = [0]*m
        for vv in v:
            cost += c[vv][0]
            for j in range(1, m+1):
                tm[j-1] += c[vv][j]
        flag = True
        for i in range(m):
            if tm[i] < x:
                flag = False
                break
        if flag:
            mn = min(cost, mn)

if mn == 10**18:
    print(-1)
else:
    print(mn)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
import numpy as np
C = np.array([0]*n)
A = np.array([[0]*m]*n)
for i in range(n):
    l = list(map(int, input().split()))
    C[i] += l[0]
    A[i] += np.array(l[1:])

def L(i):
    X = []
    for j in range(n):
        X.append(i%2)
        i = i//2
    X.reverse() 
    return np.array(X)

ans = []
for k in range(2**n):
    D = np.dot(L(k), A)
    if min(D) >= x:
        ans.append(np.dot(C, L(k)))
        
if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = float('INF')
    n, m, x = map(int, input().split())
    c = [0]*n
    a = [[0 for _ in range(m)]for _ in range(n)]
    for i in range(n):
        temp = list(map(int, input().split()))
        c[i] = temp[0]
        for j in range(m):
            a[i][j] = temp[j+1]
    for bit in range(1<<n):
        acquired = True
        cost = 0
        d = [0]*m
        for i in range(n):
            if (bit & (1 << i)):
                cost += c[i]
                for j in range(m):
                    d[j] += a[i][j]
        for k in range(m):
            if d[k] < x:
                acquired = False
        if acquired:
            ans = min(ans, cost)
    if ans == float('INF'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []
a = []
INF = 1001001001

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

ans = INF

for s in range(2 ** n):
    cost = 0
    d = [0 for i in range(m)]
    for i in range(n):
        if (s >> i) & 1:
            cost += c[i]
            for j in range(m):
                d[j] += a[i][j]
    ok = True
    for j in range(m):
        if d[j] < x: ok = False
    if ok: ans = min(ans, cost)

if ans == INF: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(n)]
l=[]
for i in range(2**n):
    l.append(format(i,'b').zfill(n))
l1=[]
for i in range(len(l)):
    s=[0]*(m+1)
    for j in range(n):
        if l[i][j]=='1':
            for k in range(m+1):
                s[k]+=c[j][k]

    for o in range(1,m+1):
        if s[o]<x:break
        if o==m:l1.append(s[0])
if len(l1)==0:print(-1) 
else:print(min(l1))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
for i in range(1<<n):
  arr = [0] * (m+1)
  for j in range(n):
    if i&(1<<j)==0: continue
    for k, l in enumerate(a[j]):
      arr[k] += l
  if all(l >= x for l in arr[1:]):
    ans = min(ans, arr[0])
print(-1 if ans == float('inf') else ans)

Submission status: Accepted

Solution code:
N,M,X=[int(x) for x in input().rstrip().split()]
l=[]

for i in range(N):
  a=[int(x) for x in input().rstrip().split()]
  l.append(a)

ans=float('inf')
falg=1


A=[0 for x in range(M)]
for i in range(2**N):
  cost=0
  flag=1
  
  for j in range(N):
    if i>>j & 1:
      now=l[j]
      cost+=now[0]
      for t in range(M):
        A[t]+=now[t+1]

  for s in range(M):
    if X<=A[s]:
      continue
    else:
      flag=0
      break
  if flag==1:
    ans=min(ans,cost)
  
  A=[0 for v in range(M)]

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

Submission status: Accepted

Solution code:
import numpy as numpy
n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')
for i in range(2 ** n):
    cost = 0
    exp = numpy.array([0] * m)
    for j, b in enumerate(books):
        if i >> j & 1:
            continue
        cost += b[0]
        exp = exp + numpy.array(b[1:])
    if (exp < x).any():
        continue
    ans = min(cost, ans)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book_list = []
for i in range(N):
    book_list.append(list(map(int, input().split())))

nedan = 0
nedan_mazi = 12*10**15
flag = 0

for i in range(2**N):

    bag = []
    for j in range(N):
        if (i >> j) & 1:
            bag.append(j)

    rikai = [0] * M
    for t in bag:
        for k in range(M):
            rikai[k] += book_list[t][k+1]

    for p in range(M):
        flag=0
        if rikai[p] < X:
            flag = 1
            break

    if flag != 1:
        nedan=0
        for s in bag:
            nedan += book_list[s][0]
    else:
        nedan = 12*10**15

    nedan_mazi = min(nedan, nedan_mazi)


if nedan_mazi == 12*10**15:
    nedan_mazi = -1

print(nedan_mazi)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

ans = INF

n,m,x = map(int,input().split())
a = [inpl() for _ in range(n)]

for i in range(1<<n):
    money = 0
    score = [0] * m
    for j in range(n):
        if i>>j&1:
            money += a[j][0]
            for k in range(m):
                score[k] += a[j][k+1]
    for s in score:
        if s < x:
            break
    else:
        ans = min(ans,money)

print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import numpy as np

data = input().split()
n = int(data[0])
m = int(data[1])
x = int(data[2])
data = []
for _ in range(n):
    data.append(np.array(list(map(int,input().split()))))

INF = 10000000
ans = INF
for b in range(2**n):
    value = np.array([0 for _ in range(m+1)])
    b = bin(b)[2:]
    for zero in range(n-len(b)):
        b = "0" + b
    for i in range(n):
        if b[i] == "1":
            value += data[i]
    ok = True
    for i in range(1,m+1):
        if value[i] < x:
            ok = False
    if ok == True and value[0] <= ans:
        ans = value[0]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X=list(map(int,input().split()))
C=[list(map(int,input().split())) for i in range(N)]
result=[]
for i in range(2**N):
    A=[]
    for j in range(N):
        if (i>>j)&1:
            A.append(C[j])
    result.append(A)
inf=float('inf')
ans2=inf

for i in result:
    D=dict()
    ans1=0
    ans3=0
    if i!=[]:
        for j in i:
            ans1+=j[0]
            for k,value in enumerate(j):
                if k!=0:
                    D[k]=D.get(k,0)+value
            
        for j in D.values():
            if j>=X:
                ans3+=1
        if ans3==M:
            ans2=min(ans2,ans1)
if ans2==inf:
    print(-1)
else:
    print(ans2)

Submission status: Accepted

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

ans = 10**8
for s in range(2**n):
    cost = 0
    d = [0] * m
    for i in range(n):
        if (s >> i & 1):
            cost += c[i]
            for j in range(m):
                d[j] += a[i][j]
    ok = True
    for j in range(m):
        if (d[j] < x):
            ok = False
    if (ok):
        ans = min(ans, cost)

if (ans == 10**8):
    print("-1")
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
books=[list(map(int,input().split())) for i in range(n)]
ans=10**10
for status in itertools.product(range(2),repeat = n):
    cnt=0
    skill=[0]*m
    for j in range(n):
        if status[j]:
            cnt+=books[j][0]
            for k in range(m):
                skill[k]+=books[j][k+1]
    if min(skill)>=x:
        ans=min(ans,cnt)
if ans==10**10:print(-1)
else:print(ans)

Submission status: Accepted

Solution code:
from __future__ import annotations

import itertools
import unittest
from dataclasses import dataclass, field, InitVar
from typing import List


def create_order_patterns(n: int):
    return itertools.product(range(2), repeat=n)


@dataclass
class Book:
    id: int
    price: int
    algorithm_points: List[int]


@dataclass
class TakahashiKun:
    border_line: int
    number_of_types_of_algorithms: InitVar[int]
    purchase_amount: int = 0
    algorithm_points: List[int] = field(init=False)

    def __post_init__(self, number_of_types_of_algorithms: int):
        # 何の本も読んでない高橋くんは各種アルゴリズムの理解度が0である！
        self.algorithm_points = [0 for _ in range(number_of_types_of_algorithms)]

    def buy_and_read(self, book: Book) -> None:
        # 高橋くんは本を読むと強くなる！
        self.purchase_amount += book.price

        self.algorithm_points = [p1 + p2 for p1, p2 in zip(self.algorithm_points, book.algorithm_points)]

    def has_read_at_least_one_book(self) -> bool:
        return self.purchase_amount > 0

    def passed_border_line(self) -> bool:
        return all([p >= self.border_line for p in self.algorithm_points])


@dataclass
class TakahashiKunCollection:
    values: List[TakahashiKun] = field(default_factory=list)

    def add(self, single_result: TakahashiKun) -> None:
        self.values.append(single_result)  # メモリ優先

    def min_purchase_amount_required_pass(self) -> int:
        passed_takahashi_list = [takahashi for takahashi in self.values if takahashi.passed_border_line()]

        if not passed_takahashi_list:
            return -1

        return min([takahashi.purchase_amount for takahashi in passed_takahashi_list])

    @staticmethod
    def create(number_of_types_of_algorithms: int,
               border_line: int, 
               book_lineup: List[Book], 
               order_patterns) -> TakahashiKunCollection:
        
        takahashi_kun_collection = TakahashiKunCollection()

        for order in order_patterns:
            single_result = TakahashiKun(border_line, number_of_types_of_algorithms)

            for idx, is_buy in enumerate(order):
                if is_buy == 1:
                    single_result.buy_and_read(book_lineup[idx])

            if single_result.has_read_at_least_one_book():
                takahashi_kun_collection.add(single_result)

        return takahashi_kun_collection


def actual(N, M, X, books_info):
    book_lineup = []

    for idx, book_info in enumerate(books_info, start=1):
        book = Book(id=idx, price=book_info[0], algorithm_points=book_info[1:])
        book_lineup.append(book)

    results = TakahashiKunCollection.create(N, X, book_lineup, order_patterns=create_order_patterns(N))

    return results.min_purchase_amount_required_pass()


N, M, X = [int(x) for x in input().split()]

books_info = []
for _ in range(N):
  book_info = list(map(int, input().split()))
  books_info.append(book_info)

print(actual(N, M, X, books_info))

Submission status: Accepted

Solution code:
from __future__ import annotations

import itertools
import unittest
from dataclasses import dataclass, field, InitVar
from typing import List


def create_order_patterns(n: int):
    return itertools.product(range(2), repeat=n)


@dataclass
class Book:
    id: int
    cost: int
    skill_points: List[int]


@dataclass
class SingleResult:
    border_line: int
    dim: InitVar[int]
    cost: int = 0
    skill_points: List[int] = field(init=False)

    def __post_init__(self, dim: int):
        self.skill_points = [0 for _ in range(dim)]

    def register(self, book: Book):
        self.cost += book.cost

        self.skill_points = [p1 + p2 for p1, p2 in zip(self.skill_points, book.skill_points)]

    def has_item(self) -> bool:
        return self.cost > 0

    def is_satisfy(self) -> bool:
        return all([p >= self.border_line for p in self.skill_points])


@dataclass
class Results:
    values: List[SingleResult] = field(default_factory=list)

    def add(self, single_result: SingleResult) -> None:
        self.values.append(single_result)  # メモリ優先

    def min_cost_ok(self) -> int:
        satisfied_books = [book for book in self.values if book.is_satisfy()]

        if not satisfied_books:
            return -1

        return min([book.cost for book in satisfied_books])

    @staticmethod
    def create(dim: int, border_line: int, book_lineup: List[Book], order_patterns) -> Results:
        results = Results()

        for order in order_patterns:
            single_result = SingleResult(border_line, dim)

            for idx, is_buy in enumerate(order):
                if is_buy == 1:
                    single_result.register(book_lineup[idx])

            if single_result.has_item():
                results.add(single_result)

        return results


def actual(N, M, X, books_info):
    book_lineup = []

    for idx, book_info in enumerate(books_info, start=1):
        book = Book(id=idx, cost=book_info[0], skill_points=book_info[1:])
        book_lineup.append(book)

    results = Results.create(N, X, book_lineup, order_patterns=create_order_patterns(N))

    return results.min_cost_ok()


N, M, X = [int(x) for x in input().split()]

books_info = []
for _ in range(N):
  book_info = list(map(int, input().split()))
  books_info.append(book_info)

print(actual(N, M, X, books_info))

Submission status: Accepted

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

ans = 10**10
for i in range(1<<n):
    score = 0
    li = [0]*m
    for j in range(n):
        LL = L[j][1:]
        
        if (i>>j)&1:
            score += L[j][0]
            for k in range(m):
                li[k] +=LL[k]
    if all(x >= p for x in li):
        ans = min(ans,score)
if ans != 10**10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from __future__ import annotations

import itertools
import unittest
from dataclasses import dataclass, field, InitVar
from typing import List


def create_buy_patterns(n: int):
    return itertools.product(range(2), repeat=n)


@dataclass
class Book:
    id: int
    cost: int
    skill_points: List[int]


@dataclass
class SingleResult:
    border_line: int
    dim: InitVar[int]
    cost: int = 0
    skill_points: List[int] = field(init=False)

    def __post_init__(self, dim: int):
        self.skill_points = [0 for _ in range(dim)]

    def register(self, book: Book):
        self.cost += book.cost

        self.skill_points = [p1 + p2 for p1, p2 in zip(self.skill_points, book.skill_points)]

    def has_item(self) -> bool:
        return self.cost > 0

    def is_ok(self) -> bool:
        return all([p >= self.border_line for p in self.skill_points])


@dataclass(frozen=True)
class Results:
    values: List[SingleResult] = field(default_factory=list)

    def add(self, single_result: SingleResult) -> None:
        self.values.append(single_result)  # メモリ優先

    def __len__(self) -> int:
        return len(self.values)

    def __getitem__(self, index: int) -> SingleResult:
        return self.values[index]

    def min_cost_ok(self) -> int:
        border_line_pass_books = [book for book in self.values if book.is_ok()]

        if not border_line_pass_books:
            return -1

        return min([book.cost for book in border_line_pass_books])

    @staticmethod
    def create(dim: int, border_line: int, book_lineup: List[Book], buy_patterns) -> Results:
        results = Results()

        for buy_pattern in buy_patterns:
            single_result = SingleResult(border_line, dim)

            for idx, is_buy in enumerate(buy_pattern):
                if is_buy == 1:
                    single_result.register(book_lineup[idx])

            if single_result.has_item():
                results.add(single_result)

        return results


def actual(N, M, X, books_info):
    book_lineup = []
    for idx, book_info in enumerate(books_info, start=1):
        book = Book(id=idx, cost=book_info[0], skill_points=book_info[1:])
        book_lineup.append(book)

    results = Results.create(N, X, book_lineup, buy_patterns=create_buy_patterns(N))

    return results.min_cost_ok()


N, M, X = [int(x) for x in input().split()]

books_info = []
for _ in range(N):
  book_info = list(map(int, input().split()))
  books_info.append(book_info)

print(actual(N, M, X, books_info))

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

inf = int(1e20)
n, m, x = map(int, input().split())
_ = [[int(x) for x in input().split()] for _ in range(n)]
CA = np.array(_, dtype=int)
ans = inf
for indices in product([0, 1], repeat=n):
    tmp = np.zeros(m + 1, dtype=int)
    for idx, be_used in enumerate(indices):
        tmp += be_used * CA[idx]
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
print(ans if ans != inf else '-1')