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 sys
import itertools
input = sys.stdin.readline
N, M, X = (int(i) for i in input().split())
#B = [int(x) for x in stdin.readline().rstrip().split()]
A = [[int(i) for i in input().split()] for i in range(N)]

combs = itertools.product(range(2), repeat=N)
ans = float('inf')
for comb in combs:
    mycomb = list(comb)
    #print(mycomb)
    cur = 0
    allm = [0]*M
    for i in range(N):
        if mycomb[i]:
            cur += A[i][0]
            for j in range(M):
                allm[j] += A[i][j+1]
    #print(allm, cur)
    for j in range(M):
        if allm[j] < X:
            break
    else:
        ans = min(ans, cur)
        #print(ans, cur)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
L=[]
ans=[0]*(M+1)
A=float("inf")
for i in range(N):
	L.append(list(map(int,input().split())))
for i in range(N):
	for j in range(1,M+1):
		ans[j]+=L[i][j]
if min(ans[1:M+1])<X:
	print(-1)
	exit()
for i in range(1,2**N+1):
	ans=[0]*(M+1)
	i+=8192
	for j in range(N):
		if ((i>>j)&1):
			for k in range(M+1):
				ans[k]+=L[j][k]
	if min(ans[1:M+1])>=X:
		A=min(ans[0],A)
print(A)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
l = [[]]*n
for i in range(n):
    l[i] = list(map(int,input().split()))
cnt_min = 10**7
for j in range(2**n):
    u = [x]*m
    cnt = 0
    b = str(bin(j))[2:].zfill(n)
    for k in range(n):
        if b[k] == '1':
            cnt += l[k][0]
            for o in range(m):
                u[o] -= l[k][o+1]
    flg = 1
    for p in range(m):
        if u[p] > 0:
            flg = 0
    if flg == 1:
        if cnt < cnt_min: 
            cnt_min = cnt
if cnt_min == 10**7:
    print(-1)
else:
    print(cnt_min)

Submission status: Accepted

Solution code:
def solve(i, cost, sums):
    global x
    if min(sums) >= x:
        global min_cost
        min_cost = min(cost, min_cost)
        return
    if i == n:
        return
    solve(i + 1, cost, list(sums))
    for i_, a in enumerate(C[i][1]):
        sums[i_] += a
    cost += C[i][0]
    solve(i + 1, cost, list(sums))


n, m, x = map(int, input().split())
C = []
ans = 0
for _ in range(n):
    __ = [int(x) for x in input().split()]
    C.append([__[0], __[1:]])
min_cost = int(1e9)
solve(0, 0, [0] * m)
print(-1 if min_cost == int(1e9) else min_cost)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

NMX = input()
NMX = NMX.split()
N = int(NMX[0])
M = int(NMX[1])
X = int(NMX[2])

CA = []
for i in range(N):
    ca = input()
    ca = ca.split()
    CA.append(ca)

CA = np.array(CA, dtype = int)
C = CA[:,0]
A = CA[:,1:]

bb = np.array(list(itertools.product([0, 1], repeat = N)))


cost = 9999999
for b in bb:
    AA = (A.T * b).T
    ss = np.sum(AA, axis=0)
    if np.all(ss >= X):
        CC = np.sum(C.T * b)
        if CC < cost:
            cost = CC

if cost == 9999999:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7

n, m, x = map(int, input().split())
prices = []
mat = []
for _ in range(n):
    nums = read_n_item()
    prices.append(nums[0])
    mat.append(nums[1:])


def check(nums):
    for num in nums:
        if num < x:
            return False
    return True


def dfs(cur, pos, price, min_price):
    if check(cur):
        min_price = min(price, min_price)
        return min_price
    if pos == n:
        return min_price

    min_price = min(dfs(cur, pos+1, price, min_price), min_price)

    nxt = [0] * len(cur)
    for i in range(len(cur)):
        nxt[i] = cur[i] + mat[pos][i]
    min_price = min(min_price, dfs(nxt, pos+1, price+prices[pos], min_price))
    return min_price

min_price = dfs([0]*m, 0, 0, float('inf'))

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

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())))
A.sort()
for n in range(1,len(A)+1):
    for conb in itertools.combinations(A, n):
        S=[0]*(M+1)
        for L in conb:
            for i in range(M+1):
                S[i] += L[i]
        if min(S[1:])>=X:
            ANS.append(S)
if ANS==[]:
    print(-1)
else:
    ANS.sort()
    print(ANS[0][0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, m, x  = map(int, input().split())
li  = [list(map(int, input().split())) for _ in range(n)]
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ans = 10**9
for i in range(2**n): # 総当り
    s = f'{i:012b}'[12-n:]

    # TODO:金額break

    rikaido = [0] * m
    price = 0
    for i2, b in enumerate(s): # 選んだやつ
        if b == '1':
            price += li[i2][0]
            for i3 in range(m): # 理解度を足す
                rikaido[i3] += li[i2][i3+1]

    # 理解してるか
    for r_ in rikaido:
        if r_ < x:
            break
    else:
        if price < ans:
            ans = price

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

Submission status: Accepted

Solution code:
import itertools


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


skills = [list(map(int,input().split())) for _ in range(n)]


zero_one_list = list(itertools.product(range(2), repeat=n))


money_list = []

for z in zero_one_list:
    sum_skills = [0] * m
    sum_money = 0
    for i in range(n):
        if z[i] == 1:
            sum_money += skills[i][0]
            sum_skills = [x + y for (x,y) in zip(sum_skills,skills[i][1:])]
        else:
            continue

    if (all(elem >= x for elem in sum_skills)):
        money_list.append(sum_money)
    else:
        continue

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

Submission status: Accepted

Solution code:
import sys
N,M,X=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
#print(L)
price=[]
list_X=[X for i in range(M)]
#print(list_X)
for i in range(2**N):
  A=[0 for i in range(M+1)]
  for j in range(N):
    if (i>>j) & 1:
      A = [x+y for (x,y) in zip(A,L[j])] 
  #print(A)
  large = 0
  for i in range(M):
    if A[i+1] >= list_X[i]:
      large += 1
  if large == M:
    price.append(A[0])
  #if A[1:] >= list_X:
    #price.append(A[0])
#print(price)
if price ==[]:
  print(-1)
else:
  print(min(price))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m, x = map(int, input().split())
L = []
J = []
for i in range(n):
    l = list(map(int, input().split()))
    L.append(l)
for i in range(2**n):
    cost = 0
    f = 0
    M = [0]*m
    for j in range(n):
        
        if (i>>j)&1 == 1:
            cost += L[j][0]
            for k in range(m):
                M[k] += L[j][k+1]
    for p in M:
        if p < x:
            f = 1
    if f == 0:
        J.append(cost)
if J != []:
  print(min(J))
else:
  print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
c=[0]*n
a=[0]*n
for i in range(n):
    ca=list(map(int,input().split()))
    c[i]=ca[0]
    a[i]=ca[1:]

ans=sum(c)+1
for i in range(2**n):
    bag=[]
    money=0
    point=np.zeros(m, dtype=int)
    for j in range(n):
        if ((i>>j) &1):
            bag.append(j)
            money+=c[j]
    for k in range(len(bag)):
        point+=a[bag[k]][:]
    if min(point)>=x:
        ans=min(ans,money)

if ans>sum(c):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A=[['' for i in range(M)] for j in range(N)]
C=[0 for j in range(N)]
check=[]
minMoney=12000001
flag=False
for i in range(N):
    x=list(map(int,input().split()))
    C[i]=x[0]
    A[i]=x[1:]
for i in range(2**N):
    count=0
    Acheck=[0 for i in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            flag=True
            count+=C[j]
            for k in range(M):
                Acheck[k]+=A[j][k]
                if Acheck[k]<X:
                    flag=False
    
    if flag:
        minMoney=min(count,minMoney)
    #print(i,"通り目", minMoney,Acheck)
if minMoney==12000001:
    print(-1)
else:
    print(minMoney)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int,input().split())) for i in range(n)]
A = []
for i in range(n):
  A.append(i)
sum =10**9+7
for i in range(1 << len(A)):
    output = []
    for j in range(len(A)):
        if ((i >> j) & 1) == 1:
            output.append(A[j])
    ans = [0]*(m+1)
    for i in output:
      ans = [x + y for (x, y) in zip(ans, a[i])]
    for j in ans[1:]:
      if j >= x:
        continue
      else: break
    else: sum = min(sum, ans[0])
if sum == 10**9+7:
  print(-1)
else:
  print(sum)

Submission status: Accepted

Solution code:
import numpy as np

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

hon = []
for _ in range(N):
    hon.append(np.array(list(map(int, input().split()))))

ans = 10**10
flag = 1
for i in range(1, 2**N):
    tmp = np.zeros(M)
    tmp_m = 0
    for j in range(N):
        if (i >> j) & 1:
            tmp = tmp + hon[j][1:]
            tmp_m += hon[j][0]
    if (tmp >= X).sum() == M:
        if tmp_m < ans:
            ans = tmp_m
            flag = 0
if flag:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# 2**N
fg = 0
cost = sum([ i[0] for i in c_list])
for i in range(2**N):
    t_cost = []
    l = [ 0 for _ in range(M)]
    for j in range(N):
        if ((i>>j) & 1 ):
            t_cost.append(c_list[j][0])
            l = [ x+y for x,y in zip(l,c_list[j][1:])]
    if len([ 0 for k in l if k < X ]) == 0:
        fg = 1
        cost = min(cost, sum(t_cost))
if fg != 0:
    print(cost)
else:
    print('-1')

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N,M,X=list(map(int,input().split()))
C=[]
A=[]
for i in range(N):
  s=list(map(int,input().split()))
  C.append(s[0])
  A.append(np.array(s[1:]))
combs=[]
lis = range(N)
for i in range(1,N+1):
  for team in itertools.combinations(lis, i):
    combs.append(team)
lp=0
for comb in combs:
  price=0
  skill=np.array([0 for i in range(M)])
  for i in comb:
    price+=C[i]
    skill+=A[i]
  if min(skill)>=X:
    if lp==0:
      lp=price
    elif lp>price:
      lp=price
if lp==0:
  print(-1)
else:
  print(lp)

Submission status: Accepted

Solution code:

def q3():
    N, M, X = [int(i) for i in input().split(" ")]
    books = []
    for i in range(N):
        values = [int(i) for i in input().split(" ")]
        C = values[0]
        A = values[1:]
        books.append([C, A])
    
    def dfs(i, points, value, values):
        if i == N:
            for p in points:
                if p < X:
                    return
            values.append(value)
            return
        dfs(i + 1, list(points), value, values)
        for ind in range(len(points)):
            points[ind] += books[i][1][ind]
        dfs(i + 1, list(points), value + books[i][0], values)
    
    point = []
    for i in range(M):
        point.append(0)
    values = []
    dfs(0, point, 0, values)
    
    if not values:
        print(-1)
    else:
        print(min(values))

q3()

Submission status: Accepted

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

ab_list=[]
for i in range(n):
    a_list=list(map(int,input().split()))
    ab_list.append(a_list)

min_val=-1

for i in range(2 ** n):
    tmp = [False] * n
    for j in range(n):
        if i >> j & 1:
            tmp[j] = True
    
    ss=[0]*m
    val=0
    for j,f in enumerate(tmp):
        if f:
            for k in range(m):
                ss[k]+=ab_list[j][1+k]

            val+=ab_list[j][0]
        
    if min(ss) >=x:
        if min_val==-1:
            min_val=val
        elif min_val>val:
            min_val=val

print(min_val)

Submission status: Accepted

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

Book = [[int(x) for x in input().split()] for j in range(n)]
Cost = 10 ** 7
for i in range(2**n):
  bag = [0 for k in range(n+1)]
 
  for j in range(n):
    if ((i >> j) &1):
      bag = [ x + y for (x,y) in zip (bag,Book[j])]
  if all(b >= x for b in bag[1:]):
    if Cost >= bag[0]:
      Cost = bag[0]
if Cost != 10 ** 7:
  print(Cost)
else:
  print(-1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
ans=float("inf")
flag2=1
c=[]
for i in range(N):
    cc=list(map(int,input().split()))
    c.append(cc)
for i in range(2**N):
    flag=0
    score=[0 for _ in range(M+1)]
    for j in range(N):
        if i>>j & 1:
            for k in range(M+1):
                score[k]+=c[j][k]
    for j in range(1,M+1):
        if score[j]<X:
            flag=1
            break
    if flag==0:
        flag2=0
        ans=min(score[0],ans)
if flag2==1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def make_patterns(num_digits):
    res = []
    for i in range(2 ** num_digits):
        res.append(format(i, 'b').zfill(num_digits))
    return res


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

patterns = make_patterns(n)

res = -1
for pattern in patterns:
    lst = list(pattern)
    cost = 0
    score = [0 for _ in range(m)]
    for i, binary in enumerate(lst):
        if "0" == binary:
            continue
        for j in range(m):
            score[j] += books[i][j + 1]
        cost += books[i][0]
    if all(map(lambda elm: elm >= x, score)):
        if res == -1:
            res = cost
        else:
            res = min(res, cost)
print(res)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X=map(int, input().split())  
y=[list(map(int,list(input().split()))) for i in range(N)]

tmp = sum([y[k][0] for k in range(N)]) + 1
ans = tmp
#print(ans)
for i in range(2**N):
  c = 0
  A=[0]*M
  A = np.array(A)
  for j in range(N):
    if ((i >> j) & 1):
      c += y[j][0]
      A += np.array(y[j][1:M+1])
  #print(A)
  if np.all(A>=X):
    ans = min(ans, c)

if ans==tmp:
  ans = -1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

C=[]
A=[]
min_price=-1

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

for j in range(2**N):
    kekka=True
    taisho=[]
    for k in range(N):
        if ((j>>k)&1):
            taisho.append(k)
    
    #理解度および値段
    price=0
    rikai=defaultdict(int)
    for l in taisho:
        price += C[l]
        for m in range(M):
            rikai[m] += A[l][m]
    
    #理解度の確認
    for n in range(M):
        if rikai[n]<X:
            kekka=False
            break
    
    #理解度が充足しているとき
    if kekka == True:
        if min_price==-1 or price<min_price:
            min_price=price

print(min_price)

Submission status: Accepted

Solution code:
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:]


min_val = sum(C)
ans = False

for bit in range(1 << N):
    R = [0] * M
    c = 0

    for i in range(N):
        if bit & (1 << i):
            c += C[i]
            for m in range(M):
                R[m] += A[i][m]

    if all([r >= X for r in R]):
        ans = True
        min_val = min(min_val, c)


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

Submission status: Accepted

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
sys.setrecursionlimit(150000)

N, M, X = map(int, sys.stdin.readline().split())
a = []
for i in range(N):
    a.append(inpl())
b = [0] * M
res = float("INF")
def dfs(cost, start, tmp):
    global res
    if min(tmp) >= X:
        res = min(res, cost)
        return res
    for i in range(start, N):
        c = tmp.copy()
        d = [i + j for i, j in zip(c, a[i][1:])]
        dfs(cost + a[i][0], i + 1, d)
    return res

ans = dfs(0,0,b)
if ans != float("INF"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,M,X=nm()
C=[0]*N
A=[[0]*M for i in range(N)]
for i in range(N):
    tmp=nl()
    C[i]=tmp[0]
    A[i][:]=tmp[1:]

r=[[0]*M for i in range(2**N)]
cm=[0]*(2**N)
for i in range(2**N):
    sum_m=0
    for j in range(N):
        if((i>>j) & 1):
            sum_m+=C[j]
            for k in range(M):
                r[i][k]+=A[j][k]
    cm[i]=sum_m

inds=list(range(2**N))
inds.sort(key=lambda x: cm[x])

ind=0
while(ind<2**N):
    flag=True
    for i in range(M):
        if(r[inds[ind]][i]<X):
            flag=False
    if(flag==True):
        print(cm[inds[ind]])
        sys.exit(0)
    ind+=1

print(-1)

Submission status: Accepted

Solution code:
import itertools

n,m,x=list(map(int,input().split()))
C,li=[],[] 
ans=[]
for i in range(n):
  c,*A=list(map(int,input().split()))
  C.append(c)
  li.append(A)
  
for i in itertools.product([0,1],repeat=n):
  money=sum([y*z for (y,z) in zip(C,i)])
  U=[0 for _ in range(m)]
  for k,j in enumerate(i):
    if j:
      U=[x+y for (x,y) in zip(U,li[k])]
  if sum([u >= x for u in U]) == m:
    ans.append(money)
    
if ans == []:
  print("-1")
else:
  print(min(ans))

Submission status: Accepted

Solution code:


def solve():

    mini = 10**9
    combs = getcombs(n)
    for com in combs:
        skill = [0] * m
        price = 0
        for i in range(n):
            if int(com[i]):
                price += c[i]
                addvec(skill, a[i])
                if min(skill) >= x:
                    mini = min(mini, price)
    if mini!=10**9:
        print(mini)
    else:
        print(-1)
    return


def getcombs(n):
    combs = []
    for i in range(2**n):
        combs.append(format(i, '#0{}b'.format(n+2))[2:])
    return combs






def addvec(a,b):
    for i in range(len(a)):
        a[i] += b[i]


#s= input()
n,m, x = [int(i) for i in input().split(" ")]
c = []
a = []
for _ in range(n):
    read = [int(i) for i in input().split(" ")]
    c.append(read[0])
    a.append(read[1:])
solve()

Submission status: Accepted

Solution code:
import itertools

N,M,X=map(int, input().split())
data=[]
ans=999999999
b=[]
b_pairs=[]
for i in range(N):
    b.append(i)
for i in range(N):
    data.append(list(map(int, input().split())))

for i in range(2,N+1):
    b_pairs+=itertools.combinations(b,i)

for i in range(N):
    flag=1
    skill=[0]*M
    for j in range(M):
        skill[j]+=data[i][j+1]
    for j in range(M):
        if skill[j]<X:
            flag=0
    if flag==1:
        ans=min(ans,data[i][0])

for i in range(len(b_pairs)):
    skill=[0]*M
    sum=0
    flag=1
    for k in range(len(b_pairs[i])):
        sum+=data[b_pairs[i][k]][0]
        for j in range(1,M+1):
            skill[j-1]+=data[b_pairs[i][k]][j]
    for h in range(M):
        if skill[h]<X:
            flag=0
    if flag==1:
        ans=min(ans,sum)

if ans==999999999:
    ans=-1
print(ans)

Submission status: Accepted

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

A=[0 for i in range(M+2)]
flag=1
ans=10**10
cnt=0
for i in range(2**N):
  flag=1
  cost=0
  for j in range(N):
    if i>>j & 1:
      now=l[N-j-1]
      cost+=now[0]
      for s in range(M):
        A[s]+=now[s+1]
  for t in range(M):
    if X<=A[t]:
      continue
    else:
      flag=0
      break
  if flag==1:
    ans=min(ans,cost)
    cnt+=1

  A=[0 for v in range(M+2)]

if cnt==0:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 10
N, M, X = map(int, input().split())
C = list()
A = list()
for n in range(N):
    ca = list(map(int, input().split()))
    C.append(ca[0])
    A.append(ca[1:])
ans = INF
for n in range(2 ** N):
    m = [0] * M
    c = 0
    for nn in range(N):
        if (n & (1 << nn)) > 0:
            c += C[nn]
            for mm in range(M):
                m[mm] += A[nn][mm]
    if all([x >= X for x in m]):
        ans = min(ans, c)
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

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

CA = []

for i in range(N):
    CA.append(list(map(int, input().split())))

CA = np.array(CA)

C = CA[:, 0]
A = CA[:, 1:]

whole = np.array(list(product([0,1],repeat=N)), np.bool)

ans_tmp = []

for p in whole:
    score = A[p].sum(axis=0)
    ans_tmp.append(score[np.where(score>=X)].shape[0]==M)

pattern = whole[ans_tmp]

score = A[whole[1]].sum(axis=0)

ans = 10**15
for p in pattern:
    tmp = C[p].sum()
    if ans > tmp:
        ans = tmp

print(ans) if ans != 10**15 else print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
c = []
A = np.array([[0]*m for _ in range(n)])
for i in range(n):
  a = list(map(int,input().split()))
  c.append(a[0])
  A[i] = np.array(a[1:])
ans = 10**18
for i in range(2**n):
  cost = 0
  u = np.array([0]*m)
  for j in range(n):
    if i >> j & 1:
      cost += c[j]
      u += A[j]
  flag = 1
  for j in range(m):
    if u[j] < x:
      flag = 0
  if flag == 1:
    ans = min(cost,ans)
if ans == 10**18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
caaa = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 7
for i in range(1, n + 1):
    for caa in list(itertools.combinations(caaa, i)):
        c = 0
        aa = [0] * m
        for j in range(i):
            c += caa[j][0]
            for k in range(m):
                aa[k] += caa[j][k + 1]
        if all(aa[l] >= x for l in range(m)):
            ans = min(c, ans)
print(-1 if ans == 10 ** 7 else ans)

Submission status: Accepted

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

INF = 10**7
ans = INF
for t in range(2**N):
    tmp = 0
    check = [X]*M
    for i in range(N):
        if (t >> i) & 1 == 1:
            tmp += CA[i][0]
            for j in range(M):
                check[j] -= CA[i][j+1]
    for ch in check:
        if ch > 0:
            break
    else:
        if tmp < ans:
            ans = tmp

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

min_total = -1
for i in range(2 ** N):
    sub = 0
    skills = [0] * M

    for j in range(N):
        if (i >> j & 0b1) == 1:
            sub += books[j][0]
            for k in range(M):
                skills[k] += books[j][k + 1]

    for k in range(M):
        if skills[k] < X:
            break
    else:
        min_total = sub if min_total == -1 else min(min_total, sub)

print(min_total)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
for i in range(n):
    a1 = [int(i) for i in input().split()]
    c1 = a1.pop(0)
    a.append(a1)
    c.append(c1)
ans = []
for bit in range(1<<n):
    d = [0]*m
    price = 0
    for i in range(n):
        mask = 1<<i
        if mask&bit:
            price += c[i]
            for j in range(m):
                d[j] +=  a[i][j]
    flag = True
    for j in d:
        if j<x:
            flag = False
    if flag:
        ans.append(price)
print(min(ans) if len(ans)>0 else -1)

Submission status: Accepted

Solution code:
N, M, X = [int(i) for i in input().split()]
Cn = []
Anm = []
for n in range(N):
  Xn = [int(i) for i in input().split()]
  Cn.append(Xn[0])
  Anm.append(Xn[1:])

min_cost = 1e100
for i in range(2**N):
  is_buy = [i >> m  & 1 for m in range(N)]
  ms = [0] * M 
  cost = 0
  for n in range(N):
    if is_buy[n] == 1:
      cost += Cn[n]
      for m in range(M):
        ms[m] += Anm[n][m]
  if min(ms) >= X:
    min_cost = min(cost, min_cost)
if min_cost == 1e100:
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
import numpy as np

def dfs(a, c, a_lis, i, total_c):
    global min_c
    if len(a_lis.shape) > 1:
        total_sum = np.sum(a_lis, axis=0)
        for j in range(len(total_sum)):
            if total_sum[j] < x:
                break
            if j == len(total_sum)-1:
                min_c.append(total_c)
    if i >= n:
        return 0
    dfs(a, c, np.vstack((a_lis, a[i])), i+1, total_c + c[i])
    dfs(a, c, a_lis, i+1, total_c)


n,m,x = map(int,input().split())
li = []
c = []
for i in range(n):
    li.append(list(map(int,input().split())))
    c.append(li[i].pop(0))
a = np.array(li)
total_sum = np.sum(a, axis=0)
for i in total_sum:
    if i < x:
        print(-1)
        exit()
min_c = []
dfs(a, c, np.zeros(m), 0, 0)
print(min(min_c))

Submission status: Accepted

Solution code:
import sys
import os
import itertools

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M,X=map(int, input().split())
    C=[0]*N
    A=[[0 for j in range(M)] for i in range(N)]
    for i in range(N):
        tmp=list(map(int, input().split()))
        C[i]=tmp[0]
        A[i]=tmp[1:]

    sum=0
    min=100000000
    A_sum=[0]*M
    for i in range(N):
        for li in itertools.combinations(range(0,N),i+1):
            # print(li)
            sum=0
            A_sum=[0]*M
            for j in li:
                sum+=C[j]
                for l in range(M):
                    A_sum[l]+=A[j][l]
            # print(sum)
            for l in range(M):
                if A_sum[l]<X:
                    break
                if l==M-1 and min>sum:
                    min=sum

    if min==100000000:
        print(-1)
    else :
        print(min)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18
#list(map(int, stdin.readline().rstrip().split()))
n,m,x = map(int, stdin.readline().rstrip().split())
numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]

rikai = [0] * m
l = [i for i in range(1,n+1)]
ans = 10**9
for i in l:
    books = list(comb(l,i))

    for j in books:
        # jを選ぶ
        pay = 0
        rikaii = rikai[:]
        for u in j:
            cost = numbers[u-1][0]
            skill = numbers[u-1][1:]
            pay += cost
            rikaii = [x + y for (x, y) in zip(rikaii, skill)]
        ok = 0
        for y in range(m):
            if rikaii[y] >= x:
                ok += 1
        if ok == m:
            ans = min(ans,pay)

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

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    costs = [0] * n
    level_up = [[] for _ in range(n)]


    for i in range(n):
        c,*exp = map(int,input().split())
        #print(exp)
        costs[i] = c
        level_up[i] = list(exp)

    mn = 99999999999999999999999999999999999999999999999

    for i in range(2 ** n):
        cost = 0
        x_check = [0] * m
        for j in range(n):
            if i >> j & 1:
                cost += costs[j]
                for k,point in enumerate(level_up[j]):
                    x_check[k] += point
        #print(cost,x_check)
        if all(map(lambda o:o>=x,x_check)):
            mn = min(mn,cost)

    if mn == 99999999999999999999999999999999999999999999999:
        print(-1)
    else:
        print(mn)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

n, m, x = map(int, input().split())
a = [0] * n
ans = 10 ** 7
c1 = [0] * m


def dfs(s, d, c):
    global ans
    c3=c.copy()
    if s == n:
        #print(d,c)
        for u in range(m):
            if c[u] < x:
                return
        ans = min(d, ans)
        #print(d,c,ans)
        return
    dfs(s + 1, d, c3)
    for k in range(m):
        c3[k] += a[s][k + 1]
    dfs(s + 1, d + a[s][0], c3)


for i in range(n):
    a[i] = list(map(int, input().split()))

c2 = [0] * m
for i in range(n):
    for j in range(m):
        c2[j] += a[i][j + 1]
for i in range(m):
    if c2[i] < x:
        print(-1)
        exit(0)

dfs(0, 0, c1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x = map(int,input().split())
c = []
total = [0] * m
ans = float('inf')
finish = False
for i in range(n):
    c.append(list(map(int,input().split())))
for i in range(1,n+1):
    for comb in itertools.combinations(c,i):
        su = np.array(comb).sum(axis=0)
        if sum(su[1:] >= x) == m:
            ans = min(ans,su[0])
if ans != float('inf'):
    print(ans)
else:
    print(-1)