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:
n, m, x = map(int, input().split())
b = []
for _ in range(n):
    c, *a = list(map(int, input().split()))
    b.append((c, a))

cost = -1
for bit in range(2 ** n):
    c = 0
    a = [0 for _ in range(m)]
    for i in range(n):
        if ((bit >> i) & 1) == 1:
            c += b[i][0]
            a = [a[j] + b[i][1][j] for j in range(m)]

    j = True
    for i in range(m):
        if x > a[i]:
            j = False
    if j:
        cost = min(cost, c) if cost >= 0 else c

print(cost)

Submission status: Accepted

Solution code:
from collections import deque

n, m, x = map(int,input().split())
books = []
costs = []

for i in range(n):
    book = list(map(int,input().split()))
    books.append(book[1:len(book)])
    costs.append(book[0])

know = [0 for i in range(m)]
money = 0
perf = 1000000000000000000000000
book_id = 0

q = deque([])
q.append([book_id,know,money])

while len(q) != 0:
    book_id, know, money = q.pop()
    know_buy = [x+y for x,y in zip(know, books[book_id])]
    money_buy = money + costs[book_id]
    temp = 0
    for i in range(m):
        if know_buy[i] >= x:
            temp += 1
    if temp == m and perf > money_buy:
        perf = money_buy
    elif temp != m and money_buy < perf and book_id+1 != n:
        q.append([book_id+1, know_buy, money_buy])
    if book_id+1 != n:
        q.append([book_id+1, know, money])

if perf != 1000000000000000000000000:
    print(perf)
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = [0] * n
A = [[] for i in range(n)]
for i in range(n):
    c = list(map(int, input().split()))
    C[i], A[i] = c[0], c[1:]

INF = 10 ** 9
ans = INF

for bit in range(0, 1 << n):
    cost = 0
    flag = True
    tmp = [0] * m
    for i in range(n):
        if bit & 1 << i:
            cost += C[i]
            for j in range(m):
                tmp[j] += A[i][j]
    for i in range(m):
        if tmp[i] < x:
            flag = False
    if flag:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import itertools

n, m, x = map(int, input().split())
A = []
ans = []

for i in range(n):
    A.append((list(map(int, input().split()))))

for j in itertools.product([0, 1], repeat=n):
    skill = [0 for s in range(m + 1)]
    k = 0
    for k in range(n):
        if j[k] == 1:
            skill = [a + b for a, b in zip(skill, A[k])]
    if all(x <= e for e in skill[1:]):
        ans.append(skill[0])

if len(ans):
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
def bitsearch(n, a, x):
  mincost = 10**10
  for b in range(2**n):
    bit = format(b, f"0{n}b")
    total = [sum([int(bit[i])*a[i][j] for i in range(n)]) for j in range(m+1)]
    # print(total)
    if min(total[1:]) >= x:
      # print(min(total[1:]), x)
      mincost = min(mincost, total[0])
  if mincost == 10**10:
    return -1
  return mincost

n, m, x = map(int, input().split())
a = []
for i in range(n):
  line = list(map(int, input().split()))
  a.append(line)
print(bitsearch(n, a, x))

Submission status: Accepted

Solution code:
import sys,itertools
N,M,X=map(int,input().split())
ALL=[]
cost=0
for i in range(N):
  listA=list(map(int,input().split()))
  ALL+=[listA]
  cost+=listA[0]
for i in range(1,M+1):
  SUM=0
  for k in range(N):
    SUM+=ALL[k][i]
  if SUM<X:
    print(-1)
    sys.exit()
cost2=10**9    
for take in range(1,N+1):
  takeL=list(itertools.combinations(list(range(N)),take))
  for t in takeL:
    for i in range(1,M+1):
      SUM=0
      cost3=0
      for k in range(take):
        SUM+=ALL[t[k]][i]
        cost3+=ALL[t[k]][0]
      if SUM<X:
        break
      if i==M:
        cost2=min(cost2,cost3)
print(cost2)

Submission status: Accepted

Solution code:
INF = 10**10
def solve(n,m,x,c,a):
    best = INF
    for mask in range(2**n):
        v = [0] * m
        cost = 0
        for i in range(n):
            if mask & (2**i):
                cost += c[i]
                for j in range(m):
                    v[j] += a[i][j]
        if min(v) >= x:
            best = min(best, cost)
    return -1 if (best == INF) else best

n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    v = list(map(int, input().split()))
    c.append(v[0])
    a.append(v[1:])
print(solve(n, m, x, c, a))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(n)]
 
import itertools as it
import math
 
cost = math.inf
for comb in it.chain(*(it.combinations(C, r) for r in range(1, n+1))):
    c, *a = map(sum, zip(*comb))
    if c < cost and min(a) >= x:
        cost = c
 
print(-1 if cost is math.inf else cost)

Submission status: Accepted

Solution code:
def resolve():
    num_books, num_algo, goal = map(int, input().split())
    books = []
    min_price = 10**8
    for i in range(num_books):
        books.append(list(map(int, input().split())))

    for i in range(2 ** num_books):
        bought = []
        for j in range(num_books):
            if ((i >> j) & 1):
                bought.append(books[j])
        total_price = 0
        skils = [0 for k in range(num_algo)]

        for book in bought:
            total_price += book[0]
            for k in range(num_algo):
                skils[k] += book[1+k]

        achieved_flag = True

        for skil in skils:
            if skil < goal:
                achieved_flag = False

        if (total_price < min_price and achieved_flag):
            min_price = total_price

    if min_price == 10**8:
        print(-1)
    else:
        print(min_price)
resolve()

Submission status: Accepted

Solution code:
def ipow(x,y):
    z = 1
    for i in range(y):
        z *= x
    return z

def make_bit(value,deg):
    bit = []
    for i in range(deg):
        bit.append(value%2)
        value = value >> 1
    return bit


n,m,x = (int(i) for i in input().split())
data  = []
result = [0] * (m+1)

ra = ipow(2,n)
ans = -1

for i in range(n):
    data.append([int(x) for x in input().split()])

for i in range(ra):
    flag = True
    result = [0 for i in range(m+1)]
    bit = make_bit(i,n)
    for j in range(n):
        if(bit[j] == 1):
            result = [x+y for(x,y) in zip(result,data[j])]
    for j in range(1,m+1):
        if result[j] < x:
            flag = False
            break
    if flag == True:
        if ans == -1 or ans > result[0]:
            ans = result[0]

print(ans)

Submission status: Accepted

Solution code:
import math
def main():
    N,M,X = map(int, input().split())
    C = [0 for j in range(N)]
    A = [[0 for j in range(M)] for i in range(N)]
    for i in range(0, N):
        l = list(map(int, input().split()))
        
        C[i] = l[0]
        A[i] = l[1:]

    res = max(C)*N
    possible = False
    for i in range(0,1<<N):
        cost= 0
        und= [0 for j in range(M)]
        for j in range(N):
            if (i>>j)&1 == 1:
                cost += C[j]
                und =list(map(lambda x,y: x+y, und, A[j]))
        
        if min(und) - X >=0 and cost <= res:
            res = cost
            possible = True

    if possible:
        print(res)
    else:
        print('-1')       

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def main():
    N, M, X = map(int, input().split())
    books = [None] * N
    costs = [0] * N
    for i in range(N):
        tmp = list(map(int, input().split()))
        costs[i] = tmp[0]
        books[i] = tmp[1:]
    ans = float("inf")
    for pattern in itertools.product([True, False], repeat=N):
        skills = [0] * M
        cost = 0
        for i in range(N):
            if pattern[i]:
                for j in range(M):
                    skills[j] += books[i][j]
                cost += costs[i]
        if min(skills) >= X:
            ans = min(ans, cost)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


MAX = 100000000000	

def func(cost,a,i):
	if min(a) >= X:
		return cost
	elif i == N:
		return MAX
	total_A = [x+y for (x,y) in zip(a,A[i])]
    
	return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))
	
ans = func(0,[0]*M,0)

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

Submission status: Accepted

Solution code:
import itertools

N,M,X=map(int,input().split())
C=[]*N


A=[]
seq=[]
for i in range(N):
    A.append(list(map(int,input().split())))
    seq.append(i)
rikai=[0 for i in range(M+1)]

min=-1
count=0


for i in range(1,N+1):
    kumi=list(itertools.combinations(seq,i))
    #print(kumi)
    for j in kumi:

        for n in list(j):

            for k in range(M+1):
                rikai[k]=A[n][k]+rikai[k]

        for k in range(1,len(rikai)):
            if(X<=rikai[k]):

                count=count+1

            rikai[k]=0
        if(count==len(rikai)-1):

            if(rikai[0]<min or min==-1):
                min=rikai[0]

        rikai[0]=0
        count=0
print(min)

Submission status: Accepted

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

c = []
a = []
for i in range(len(ca)):
    c.append(ca[i][0])
    a.append(ca[i])
    del a[i][0]

ans = 12345678
for i in range(2 ** n):
    cost = 0
    level = [0] * m
    for j in range(n):
        if((i>>j)&1):
            cost += c[j]
            for k in range(m):
                level[k] += a[j][k]
    flag = True
    for k in range(m):
        if(level[k] < x):
            flag = False
    if(flag):
        ans = min(ans,cost)
if(ans == 12345678):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
C = np.zeros(n, dtype=int)
AA = np.zeros([n, m], dtype=int)
for i in range(n):
    CA = np.array(list(map(int, input().split())))
    C[i] = CA[0]
    AA[i] = CA[1:]

ans = np.inf
for bit in range(2**n):
    Skill = np.zeros(m, dtype = int)
    cost = 0
    for i in range(len(AA)):
        mask = 1 << i
        if bit & mask:
            Skill += AA[i]
            cost  += C[i]
    if all(map(lambda skill: skill >= x, Skill)):
#        print(Skill, cost)
        ans = min(ans, cost)
if ans != np.inf:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
Money = 2e6
for i in range(2 ** N):
    P = [0] * M
    m = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(len(P)):
                P[k] += CA[N - 1 - j][k + 1]
            m += CA[N - 1 - j][0]
    ok = True
    for k in range(M):
        if P[k] < X:
            ok = False
    if ok:
        Money = min(Money, m)
if Money == 2e6:
    print('-1')
else:
    print(Money)

Submission status: Accepted

Solution code:
import itertools

n, m, x = [int(i) for i in input().split()]
a = []
c = []
for i in range(n):
    temp = [int(j) for j in input().split()]
    c.append(temp[0])
    a.append(temp[1:])

ans = 9999999
for i in range(2**n):
    
    # 参考書パターンの作成
    book_list = []
    amount = 0
    for j in range(n):
        if i >> j & 1:
            book_list.append(a[j])
            amount += c[j]
    
    # 習得するスキルの計算
    skill_list = [0] * m
    for book in book_list:
        for skill_index in range(len(book)):
            skill_list[skill_index] += book[skill_index]
    
    # スキルチェック
    check = True
    for j in skill_list:
        if j < x:
            check = False
            break
        else:
            pass
        
    # 価格の計算
    if check:
        ans = min(ans, amount)

# 答えの表示
if ans == 9999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math

def to_binary(n,N):
    B=[]
    for i in range(N):
        B=[n%2]+B
        n//=2

    return B

def list_sum(A,N,M,L):
    U=[0 for j in range(M)]
    
    for i in range(N):
        if L[i]==1:
            for j in range(M):
                U[j]+=A[i][j]
    return U

def inner(A,B):
    n=len(A)
    S=0
    for i in range(n):
        S+=A[i]*B[i]
    return S

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:])

J=math.inf
for i in range(2**N):
    L=to_binary(i,N)
    U=list_sum(A,N,M,L)
    if min(U)>=X:
        J=min(J,inner(C,L))

if J==math.inf:
    print(-1)
else:
    print(J)

Submission status: Accepted

Solution code:
N, M , X = map(int, input().split())
C = [0 for i in range(N)]
A = [[]for i in range(N)]


for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    A[i] = temp[1:]

def solve():
    ans = float('inf')
    # Total: O(2^N*N*M)
    total = 1 << N
    for mask in range(total):  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        
        for i in range(N):  #O(N)
            if (mask >> i) & 1:
                cost += C[i]
                for j in range(M): #O(M)
                    L[j] += A[i][j]
            
        ok = True
        for i in range(M):
            if L[i] < X: 
                ok = False
        #print(L, cost, ok)
        if ok:
            ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []
a = []
for _ in range(n):
  ca = list(map(int, input().split()))
  c.append(ca[0])
  a.append(ca[1:])
  
ans = 10**9
for cnt in range(2**n):
  costs = 0
  skills = [0 for _ in range(m)]
  cnt = ('{:0'+str(n)+'b}').format(cnt)
  for i in range(n):
    if cnt[i] == '1':
      costs += c[i]
      for j in range(m):
        skills[j] += a[i][j]
  if len(list(filter(lambda skill: skill>=x, skills))) == m:
    ans = min(ans, costs)
print(ans if ans != 10**9 else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = [0]*n
A = [[0]*m for i in range(n)]

for i in range(n):
    C[i], *A[i] = map(int, input().split())
    
ans = sum(C)
F = False
for i in range(1, 2**n+1):
    combs = bin(i)[2:].zfill(n)
    tmp_ans = 0
    tmp_skill = [0]*m
    f = True
    for comb_i, comb in enumerate(combs):
        if comb=='1':
            tmp_ans += C[comb_i]
            tmp_skill = [t+a for t, a in zip(tmp_skill, A[comb_i])]
    for t in tmp_skill:
        if t < x:
            f = False
            break
            
    if f:
        ans = min(ans, tmp_ans)
        F = True
    
print(ans if F else -1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
for c in range(n):
    a.append([int(x) for x in input().split()])
s=10**7
for d in range(2**n):
    p=0
    q=[0]*m
    for e in range(n):
        if (d%(2**(e+1)))//(2**e)==1:
            p+=a[e][0]
            for f in range(m):
                q[f]+=a[e][f+1]
    if s<p:
        continue
    r=0
    for f in range(m):
        if q[f]<x:
            r=1
            break
    if r==0:
        s=p
if s==10**7:
    print(-1)
else:
    print(s)

Submission status: Accepted

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, m, x = nm()
li = [np.array(nl()) for _ in range(n)]
ans = 10 ** 10
comp = np.array([x for _ in range(m)])
for i in range(1 << n):
    sum = np.array([0 for _ in range(m + 1)])
    now = i
    for j in range(n):
        di = now % 2
        now = now >> 1
        if di == 1:
            sum += li[j]
    
    if all(sum[1:m+1] >= comp):
        ans = min(ans, sum[0])
if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m, x = list(map(int, input().split()))

books=[]
for _ in range(n):
    tmp=list(map(int, input().split()))
    books.append(tmp)

ans=None
# 各参考書を選ぶ、選ばないパターンをすべて試す
for bit in range(2**n):
    # 洗濯した参考書の合計コスト、スキルを格納
    total_skill=[0]*(m)
    total_cost=0
    for shift in range(n):
        # ビットの立っている参考書を買う
        if (bit>>shift)&1:
            book=books[shift]
            for i, data in enumerate(book[1:]):
                total_skill[i]+=data
            total_cost+=book[0]
                
#    print('total_cost=',total_cost ,'total_skill=', total_skill)
    # スキルがx以上かチェック
    if all([s>=x for s in total_skill]):
        if not ans or ans > total_cost:
            ans=total_cost

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

Submission status: Accepted

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

import itertools as it
import math

cost = math.inf
for comb in it.chain(*(it.combinations(C, r) for r in range(1, n+1))):
    c, *a = map(sum, zip(*comb))
    if c < cost and min(a) >= x:
        cost = c

print(-1 if cost is math.inf else cost)

Submission status: Accepted

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

posibilities = []

for _ in range(n):
    book = list(map(int, input().split()))
    b = posibilities[:]
    for i in b:
        posibilities.append([z+y for z, y in zip(i, book)])
    posibilities.append(book)

posibilities.sort(key=lambda i: i[0])

for i in posibilities:
    for j in i[1:]:
        if j < x:
            break
    else:
        print(i[0])
        break
else:
    print(-1)

Submission status: Accepted

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

posibilities = []

for _ in range(n):
    book = list(map(int, input().split()))
    b = posibilities[:]
    for i in b:
        posibilities.append([z+y for z, y in zip(i, book)])
    posibilities.append(book)

posibilities.sort(key=lambda i: i[0])

for i in posibilities:
    for j in i[1:]:
        if j < x:
            break
    else:
        print(i[0])
        break
else:
    print(-1)

#left = -1
#right = len(posibilities)-1
#
#while right-left > 1:
#    mid = (left+right)//2
#    for i in posibilities[mid][1:]:
#        if i < x:
#            left = mid
#            break
#    else:
#        right = mid
#
#for i in posibilities[right]:
#    if i < x:
#        print(-1)
#        break
#else:
#    print(posibilities[right][0])

Submission status: Accepted

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

import itertools as it
import math

cost = math.inf
for comb in it.chain(*(it.combinations(C, r) for r in range(1, n+1))):
    c, *a = map(sum, zip(*comb))
    if min(a) >= x:
        cost = min(cost, c)

if cost is not math.inf:
    print(cost)
else:
    print(-1)

Submission status: Accepted

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

ans = 10**9
for i in range(1, n+1):
  for j in combinations(ca,i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    #if all(t[num] >= x for num in range(1,m)):
    if min(t[1:]) >= x:
      ans = min(ans, t[0])

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

Submission status: Accepted

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

min_cost = []
for k in range(2 ** n):
    cost = 0
    und = [0 for _ in range(m)]
    for i in range(n):
        if (k >> i) & 1 == 1:
            cost += a[i][0]
            for j in range(m):
                und[j] += a[i][j + 1]
    for j in range(m):
        if und[j] < x:
            break
    else:
        min_cost.append(cost)

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

all_df = np.zeros((1,M+1))
for n in range(N):
  A = [int(i) for i in input().split()]
  all_df = np.vstack([all_df, np.array(A).reshape(1,-1)])

all_df = all_df[1:]

now_cost = 10**9
for bins in itertools.product([0,1], repeat=N):
  prod = all_df[np.array(bins).astype(bool)].sum(axis=0)
  #print(prod)
  if (X > prod[1:]).sum() > 0:
    pass
  else:
    if prod[0] < now_cost:
      now_cost = prod[0]

if now_cost == 10**9:
  print(-1)
else:
  print(int(now_cost))

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c_lst = [0]*n
a_lst = [0]*n 
for i in range(n):
    lst = list(map(int,input().split()))
    c_lst[i] = lst[0]
    a_lst[i] = lst[1:]

ryoukin = float("inf")

for i in range(2**n):
    temporary = 0
    rikaido = [0]*m
    for j in range(n):
        if i&(1<<j):
            temporary += c_lst[j]
            for k in range(m):
                rikaido[k] += a_lst[j][k]
    
    for j in rikaido:
        if j >= x:
            continue
        else:
            break #この段階でrikaidoがxを超えないものがあれば次へ（？）
    else:#breakでループ抜けなかった場合
        if temporary < ryoukin:
            ryoukin = temporary

if ryoukin != float("inf"):
    print(ryoukin)
else:
    print("-1")

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
costlst = []
scorelst = []
ans = float("inf")
for _ in range(n):
    cost,*score = map(int,input().split())
    costlst.append(cost)
    scorelst.append(score)
for i in range(2**n):
    cost = 0
    defaultscore = [0]*m
    for j in range(n):
        if (i>>j)&1:
            cost += costlst[j]
            for k in range(m):
                defaultscore[k] += scorelst[j][k]
    if all([defaultscore[p] >= x for p in range(m)]):
            ans = min(ans,cost)
        
            
                
                
                 
print(ans if ans != float("inf") else "-1")

Submission status: Accepted

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

p = []
u = []

for i in range(N):
  t = list(map(int, input().split()))
  p.append(t[0])
  u.append(t[1:])

candidate = []
for i in range(1, N+1):
  for comb in itertools.combinations(range(N), i):
    price = 0
    understand = [0]*M
    for j in range(i):
      price += p[comb[j]]
      understand = [x + y for (x, y) in zip(understand, u[comb[j]])]
    if all(elem >= X for elem in understand):
      candidate.append(price)

if candidate == []:
  print(-1)
else:
  print(min(candidate))

Submission status: Accepted

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

A=[[] for _ in range(n)] #Aでn個
c=[0]*n #c={0,0,...,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:#アルゴリズムxに到達していない
            ok=False
    if ok:
        ans=min(ans,cost_sum)
if ans==INF:
    ans=-1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

prices = []
for i in range(1, N+1):
    for to_buy in combinations(books, i):
        _b = list(zip(*to_buy))
        _price = sum(_b[0])
        _points = _b[1:]
        if all([True if sum(x) >= X else False
                for x in _points]):
            prices.append(_price)

print(min(prices) if len(prices) else '-1')

Submission status: Accepted

Solution code:
def solve(string):
    import numpy
    from itertools import product
    n, m, x, *ca = map(int, string.split())
    ca = numpy.array(ca).reshape((-1, m + 1)).T
    c, a = ca[0], ca[1:]
    ans = n * 10**5 + 1
    for b in product([0, 1], repeat=n):
        b = numpy.array(b)
        if (a @ b.T).min() >= x:
            ans = min(ans, c @ b.T)
    return str(ans if ans <= n * 10**5 else -1)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

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


def book_comb_test(book_comb):
    for skill_ind in range(M):
        skill_point = 0
        for book in book_comb:
            skill_point += book[skill_ind+1]
        if skill_point < X:
            return False
    return True


min_cost = float('inf')
bit_num = 2**N
for i in range(bit_num):
    book_comb = [books[j] for j in range(N) if (i >> j) & 1]
    if book_comb_test(book_comb):
        cost_sum = 0
        for k in book_comb:
            cost_sum += k[0]
        min_cost = min(min_cost, cost_sum)
print(min_cost if min_cost != float('inf') else -1)

Submission status: Accepted

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

n, m, x = [int(x) for x in input().split()]
C = []
A = []
for _ in range(n):
    c, *a = [int(x) for x in input().split()]
    C.append(c)
    A.append(a)
ans = float("inf")
for i in range(2**n):
    i_bin = bin(i)[2:].zfill(n)
    up = [0]*m
    cost = 0
    for j in range(n):
        if i_bin[j] == "1":
            cost += C[j]
            for k in range(m):
                up[k] += A[j][k]
    flag = 1
    for l in up:
        if l < x:
            flag = 0
            break
    if flag:
        ans = min(ans, cost)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def min_needed_value(values, skills, X):
    import sys
    ans = sys.maxsize
    for i in range(2**len(values)):
        get_skill = [0] * len(skills[0])
        get_value = 0
        for j in range(len(values)):
            if (i >> j) & 1:
                get_skill = [x + y for (x, y) in zip(get_skill, skills[j])]
                get_value += values[j]
        # print(i, get_skill, get_value)
        if all([s >= X for s in get_skill]): ans = min(ans, get_value)
    if ans == sys.maxsize: return -1
    else: return ans

def main():
    N, M, X = map(int, input().split())
    values = []
    skills = []
    for _ in range(N):
        Book = list(map(int, input().split()))
        values.append(Book[0])
        skills.append(Book[1:])
    print(min_needed_value(values, skills, X))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = 9**9
flag = False

for i in range(2**n):# Yes Or No で　2のn乗
    cost = 0
    a = [0]*m
    for j in range(n):
        if (i >> j) & 1: # を n 回右にシフトして 1 と論理積を取る（最下位の桁が 1 かチェック）
            cost += c[j][0]
            for k in range(m):
                a[k] += c[j][k+1]
    if min(a) >= x:
        flag = True
        ans = min(ans, cost)

print(ans if flag else -1)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
N,M,X = list(map(int, input().split()))
C = [0] * N
A = []

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

C = np.array(C)
A = np.array(A)

ans = -1
for pt in product([0,1], repeat = N):
  p = np.array(pt)  
  #print(C.dot(p))
  #print(p.dot(A))
  rikai = p.dot(A)
  if min(rikai) >= X:
    ans = C.dot(p) if ans == -1 else min(ans, C.dot(p))
  
print(ans)

Submission status: Accepted

Solution code:
#input data
n,m,x = map(int, input().split())
A=[]
C=[]
inf = 10**9
result = inf
#
for _ in range(n):
	CA = list(map(int, input().split()))
	C.append(CA[0])
	A.append(CA[1:])
for i in range(1<<n):
	rikaido = [0]*m
	cnt = 0	
	for j in range(n):
		if (i>>j)&1:
			for k in range(m):
				rikaido[k] += A[j][k]
			cnt += C[j]
		else:
			pass
	if min(rikaido)>=x:
		result = min(result, cnt)
if result== inf:
	print(-1)
else:
	print(result)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

C = [None] * N
A = [None] * N
for i in range(N):
    inp = list(map(int, input().split()))
    C[i] = inp[0]
    A[i] = inp[1:]

C = np.array(C)
A = np.array(A)
ans = C.sum() + 1

for choices in product((True, False), repeat=N):
    choices = np.array(list(choices), dtype=bool)
    if np.all(A[choices, :].sum(axis=0) >= X):
        ans = min(ans, C[choices].sum())

if ans == C.sum() + 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# Problem C - Skill Up

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

# initialization
min_cost = float("INF")
is_ok = False
pattern = []
for i in range(2**N):
    p = [0]*N
    for j in range(N):
        if (i>>j)&1==1:
            p[j] = 1
    pattern.append(p)

# check
for p in pattern:
    tmp_cost = 0
    tmp_list = [0] * M
    tmp_ok = True
    for i in range(N):
        if p[i]==0:
            continue

        tmp_cost += book_list[i][0]
        for j in range(1, M+1):
            tmp_list[j-1] += book_list[i][j]
    for t in tmp_list:
        if t<X:
            tmp_ok = False
            break
    if tmp_ok:
        is_ok = True
        min_cost = min(min_cost, tmp_cost)

# output
if is_ok:
    print(min_cost)
else:
    print(-1)