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())

A = []
for i in range(N):
    a = []
    for m in map(int, input().split()):
        a.append(m)
    A.append(a)

min_cost = float("INF")

for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            for d in [0, 1]:
                for e in [0, 1]:

                    for f in [0, 1]:
                        for g in [0, 1]:
                            for h in [0, 1]:
                                for i in [0, 1]:
                                    for j in [0, 1]:

                                        for k in [0, 1]:
                                            for l in [0, 1]:

                                                x = {}
                                                for m in range(1, M + 1):
                                                    x[m] = 0
                                                cost = 0
                                                if a == 1 and len(A) >= 1:
                                                    cost += A[0][0]
                                                    for m in range(1, M+1):
                                                        x[m] += A[0][m]
                                                if b == 1 and len(A) >= 2:
                                                    cost += A[1][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[1][m]
                                                if c == 1 and len(A) >= 3:
                                                    cost += A[2][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[2][m]
                                                if d == 1 and len(A) >= 4:
                                                    cost += A[3][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[3][m]
                                                if e == 1 and len(A) >= 5:
                                                    cost += A[4][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[4][m]

                                                if f == 1 and len(A) >= 6:
                                                    cost += A[5][0]
                                                    for m in range(1, M+1):
                                                        x[m] += A[5][m]
                                                if g == 1 and len(A) >= 7:
                                                    cost += A[6][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[6][m]
                                                if h == 1 and len(A) >= 8:
                                                    cost += A[7][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[7][m]
                                                if i == 1 and len(A) >= 9:
                                                    cost += A[8][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[8][m]
                                                if j == 1 and len(A) >= 10:
                                                    cost += A[9][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[9][m]

                                                if k == 1 and len(A) >= 11:
                                                    cost += A[10][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[10][m]
                                                if l == 1 and len(A) >= 12:
                                                    cost += A[11][0]
                                                    for m in range(1, M + 1):
                                                        x[m] += A[11][m]

                                                success = True
                                                for m in range(1, M + 1):
                                                    if x[m] < X:
                                                        success = False
                                                        break

                                                if success:
                                                    if cost < min_cost:
                                                        min_cost = cost

if min_cost == float("INF"):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

lis_C = np.array(list(map(lambda x: x[0], lis_all)))
lis_A = np.array(list(map(lambda x: x[1:], lis_all)))

row_idx = []
bools = [True,False]
for boollis in itertools.product(bools, repeat=N):
    row_idx.append(list(boollis))


c_min = lis_C.sum()+100
for i in range(len(row_idx)):
    if all(lis_A[row_idx[i]].sum(axis=0) >= X):
        c_min = min(lis_C[row_idx[i]].sum(), c_min)
if c_min > lis_C.sum():
    ans = -1
else :
    ans = c_min
print(ans)

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())))
xx = []    
ans = []
for i in range(2**N):
    ans.append(((bin(i))[2:]).zfill(N))
tmp = [0]*(M+1)
cost = []
for a in ans:
    for i in range(N):
        if a[i] == '0':
            for j in range(M+1):
                tmp[j] += CA[i][j]
    xx.append(tmp)
    tmp = [0]*(M+1)
aa = 0
for L in xx:
    for i in range(1,M+1):
        if L[i] >= X:
            aa += 1
    if aa == M:
        cost.append(L[0])
    aa = 0

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X=map(int,input().split())
ls = np.array([np.array(list(map(int,input().split()))) for i in range(N)])
# print(ls)
mn = -1
for i in range(1,1+N):
  for v in itertools.combinations(ls, i):
    #print(v)
    ln = len(v)
    ans = 0
    for k in range(ln):
      ans+=v[k]
    # print(ans)
    if np.count_nonzero(ans[1:] >= X) ==M:
      if mn == -1:
        mn = ans[0]
      else:
        mn = min(mn,ans[0])
    
print(mn)

Submission status: Accepted

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

import itertools
z = itertools.product([0,1],repeat=n)
t = []
s = []
for i in z:
    t = [0 for k in range(m)]
    cum=0
    for j in range(n):
        if i[j]==1:
            for k in range(m):
                t[k]+=u[j][k+1]
            cum+=u[j][0]
    for b in t:
        if b<x:
            break
    else:
        s.append(cum)
if len(s) !=0:
    print(min(s))
else:
    print(-1)

Submission status: Accepted

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

dp_list = ([0]*m)*(n+1)

ans = 10**7

def dp(i,cost,rikai):
    global ans
    frag = True
    tmp = [j for j in rikai]
    for j in range(m):
        if tmp[j] < x:
            frag = False
    if frag == True:#理解度を上回った
        ans = min(ans,cost)
        pass
    if i == n:#すべての本を買ったとき
        if frag == True:
            ans = min(ans,cost)
    else:
        dp(i+1,cost,tmp)#次の本を買わない
        for j in range(m):
            tmp[j] += s[i+1][j+1]
        dp(i+1,cost+s[i+1][0],tmp)#次の本をかう
            

dp(0,0,[0]*m)

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

Submission status: Accepted

Solution code:
import math

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

tbs = []
for i in range(N):
    arr = list(map(int, input().split()))
    tbs.append(arr)
tbs.reverse()

m = -1
for i in range(2 ** N):
    _sum = [0] * (M + 1)
    for s in range(N):
        bit = (i >> s) & 1
        if bit == 0:
            continue
        for j in range(len(_sum)):
            _sum[j] += tbs[s][j]
    if min(_sum[1:]) < X:
        continue
    if m == -1 or m > _sum[0]:
        m = _sum[0]        

print(m)

Submission status: Accepted

Solution code:
import itertools

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

C = []
A = []
for _ in range(n):
    a = list(map(int, input().split()))
    C.append(a[0])
    A.append(a[1:])

ans = []
for i in range(n):
    for combination in list(itertools.combinations(range(n), i+1)):
        # print(combination)
        total = 0
        li = [0] * m
        for j in combination:
            total += C[j]
            for k in range(m):
                li[k] += A[j][k]
        flag = True
        for l in range(m):
            if li[l] < x:
                flag = False
        if flag:
            ans.append(total)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
def hantei(ls, X):
    dekita=True
    for i in ls:
        if i < X:
            dekita=False
    if dekita==True:
        return True
    else:
        return False


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

keihi_rireki=[]
for i in range(2**N):
    rikaido=[0]*M
    keihi=0
    dekita=False
    for j in range(N):
        if((i>>j) & 1):
            keihi=keihi+hon[j][0]
            for k in range(M):
                rikaido[k]=rikaido[k]+hon[j][k+1]
    if hantei(rikaido, X)==True:
        keihi_rireki.append(keihi)

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

Submission status: Accepted

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

LIST = []
for i in range(2**N):
    L = []
    for j in range(N):
        if((i>>j) & 1):
            L.append(shop[j])
    LIST.append(L)
    
ans = 10**18

for tmp in LIST:
    tmp = np.array(tmp)
    isOK = np.sum(tmp,axis=0)
    dame = False
    if len(tmp)>0:
#         print(tmp)
        for item in isOK[1:]:
            if item < X:
                dame = True
        if dame == False:
            ans = min(ans,isOK[0])
        
if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0]*N
S = [0]*N

for i in range(N):
    c, *s = map(int, input().split())
    C[i] = c
    S[i] = list(s)

ans = 10**7
for i in range(2**N):
    num = i
    data = [0]*M
    cost = 0
    for j in range(N):
        if num&1 == 1:
            for k in range(M):
                data[k] += S[j][k]
            cost += C[j]
        num >>= 1
    if min(data) >= X:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
import numpy as np
from collections import deque
from itertools import combinations
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
    n,m,x=ints()
    ca=[]
    val=[]
    for _ in range(n):
        inp=ints()
        ca.append(inp)
        flg=1
        for i in range(1,m+1):
            if inp[i]<x:
                flg = 0
        val.append(inp[0]) if flg==1 else None
    for num in range(2,n+1):
        for v in combinations(ca,num):
            vnp = np.array(v)
            s=vnp.sum(axis=0)
            flg=1
            for i in range(1,m+1):
                if s[i]<x:
                    flg = 0
            val.append(s[0]) if flg==1 else None
    
    print(-1 if not val else min(val))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    A = np.zeros((N,M+1))
    for i in range(N):
        A[i] = [int(next(tokens)) for _ in range(M+1)]
    
    min_c = [10000000]

    def dfs(k, dep):
        if dep == N-1:
            if (k[1:]>=X).all():
                min_c[0] = min(min_c[0], k[0])
            elif ((k+A[dep])[1:]>=X).all():
                min_c[0] = min(min_c[0], k[0]+A[dep][0])
        else:
            dfs(k+A[dep],dep+1)
            dfs(k,dep+1)
    
    dfs(np.zeros(M+1), 0)
    
    if min_c[0] != 10000000:
        print(int(min_c[0]))
    else:
        print(-1)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# C
import itertools
n, m, x = map(int, input().split())
ca = [list(map(int, input().split()))for i in range(n)]
l = []
ans = 1e10
for i in range(1, n+1):
    for j in itertools.combinations(range(n), i):#ｎまでの組み合わせ
        # print(j)
        tmp = 0 #金額zc
        li = [0] * m#理解度li
        for k in j:#k番目の参考書
            # print(k)
            tmp += ca[k][0]#金額を加える
            for o in range(m):#場合jの時のkの参考書を読んだときの理解度を足す
                # print(o)
                li[o] += ca[k][o + 1]#理解度を足す
        # print(li)
        count = 0  #理解度カウンターm-1 まで
        for p in li:
            # print(count)
            if p >= x:#全ての理解度がx以上
                count += 1
            else:
                break
        # print(count,m)
        if count == m:#理解度カウンターがmになる
            # print(count,m,j)
            ans = min(ans, tmp)#金額が低い
if ans != 1e10:# 合計金額としては高すぎる>ならば一度も理解が追いついていない>-1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M, X = list(map(int, input().split()))
A = []
C = []
for i in range(N):
    _CA = list(map(int, input().split()))
    _C = _CA[0]
    _A = _CA[1:]
    A.append(_A)
    C.append(_C)

A = np.array(A)
C = np.array(C)
result = -2
A_sum = A.sum(axis=0)
if A_sum.min() < X:
    result = -1
else:
    n = np.array(list(range(N)))
    money_min = C.sum()
    for i in reversed(n + 1):
        is_enough = False
        comb = itertools.combinations(n, i)
        for _c in comb:
            c = np.array(_c)
            _A = A[c]
            _C = C[c]
            _score = _A.sum(axis=0)
            _money = _C.sum()
            if _score.min() >= X:
                is_enough = True
                if _money < money_min:
                    money_min = _money
        if not is_enough:
            break
    result = money_min
print(result)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
t = []
for i in range(n):
  ti = list(map(int,input().split()))
  t.append(ti)
mn = float("inf")
flag = False
for i in range(2**n):
  cost = 0
  a =[0]*m
  j = 0
  while i > 0:
    if i%2 == 1:
      cost += t[j][0]
      for k in range(m):
        a[k] += t[j][1+k]
    i = i//2
    j += 1
  if min(a)>=x:
    flag = True
    if cost < mn:
      mn = cost
if flag:
  print(mn)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10*7)

def bit_fullsearch(target):
    n = len(target)
    ret = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if (i>>j)&1:
                tmp.append(target[j])
        ret.append(tmp)
    return ret

n,m,x = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')

for l in bit_fullsearch(lst):
    tmp = [0 for _ in range(m+1)]
    for k in l:
        for i in range(m+1):
            tmp[i] += k[i]
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
print(ans if ans!=float('inf') else -1)

Submission status: Accepted

Solution code:
import numpy as np

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

books = []
for i in range(n):
    l = [int(x) for x in input().split(' ')]
    books.append(l)

patterns = []
for i in range(2**n):
    tmp = [False] * n
    for j in range(n):
        if ((i >> j) & 1):
            tmp[j] = True
    patterns.append(tmp)

price = []
for pattern in patterns:
    info = np.array([0]*(m+1))
    for i in range(n):
        if (pattern[i] == True):
            l = np.array(books[i])
            info += l
    else:
        if (min(info.tolist()[1:]) >= x):
            price.append(info.tolist()[0])
            
if (len(price) == 0):
    print(-1)
else:
    print(min(price))

Submission status: Accepted

Solution code:
import itertools

n,m,x=map(int,input().split())
ca=[0]*n
num=[]
ls=[]
last=[]
test=0
ng=0
money=0
for i in range(n):
  ca[i]=input().split()
  num.append(i)
  
for j in range(1,n+1):
  ls=list(itertools.combinations(num,j))
  
  for k in range(len(ls)):
    test=0
    money=0
    ng=0
    for l in range(m):
      test=0
      for p in range(j):
        test+=int(ca[ls[k][p]][l+1])
      if test<x:
        ng+=1
    if ng==0:
      for q in range(j):
        money+=int(ca[ls[k][q]][0])
      last.append(money)

if len(last)>0:
  print(str(min(last)))
else:
  print("-1")

Submission status: Accepted

Solution code:

#!/usr/bin/env python3

import sys
import pprint
import itertools

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, m, x = map(int, sys.stdin.readline().split())
	c = []
	a = []
	for i in range(n):
		ci, *ai = map(int, sys.stdin.readline().split())
		c.append(ci)
		a.append(ai)
	ans = 10**9
	log.print(a)
	for i in range(2**n):
		cost = 0
		rikai = [0]*m
		case = []
		for j in range(n):
			case.append(i>>j & 1)
		for j in range(n):
			if not case[j]:
				continue
			cost += c[j]
			for k in range(m):
				rikai[k] += a[j][k]
		# log.print(case, rikai, len(list(filter(lambda z:z>=x, rikai))))
		if len(list(filter(lambda z:z>=x, rikai))) == m:
			ans = min(cost, ans)
	if ans == 10**9:
		print(-1)
		exit()
	print(ans)





main()

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
CA = []
money = 10**7

for i in range(n):
  ca = list(map(int,input().split()))
  CA.append(ca)
  
CA = np.array(CA)
for i in range(2**n):
  tmp = 0
  X = np.array([0]*m)
  for j in range(n):
    if (i>>j)&1:
      X += CA[j][1:]
      tmp += CA[j][0]
  N = len([1 for z in X if z>=x])
  if N == m:
    money = min(money,tmp)

if money != 10**7:
  print(money)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy 

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

price = []
tmp = []

for i in range(N):
  _ = list(map(int, input().split()))
  price.append(_[0])
  tmp.extend(_[1:])
price = numpy.array(price)
learn = numpy.array(tmp).reshape((N, M))

if min(numpy.sum(learn, axis=0)) < X:
  print(-1)
else:
  success_combs = []
  for k in range(1, N+1):
    for comb in itertools.combinations(range(N), k):
      if min(numpy.sum(learn[comb, :], axis=0)) >= X:
        success_combs.append(comb)

  min_p = None
  for comb in success_combs:
    p = sum(numpy.take(price,comb))
    if min_p is None:
      min_p = p
    elif min_p > p:
      min_p = p
  print(min_p)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
12 5 22
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
100 3 7 5 3 1 3 7 5 3 1 12
164 3 7 5 3 1 3 7 5 3 1 12
'''

def solve(l,n,m,x):
	totPossible = defaultdict(int)
	for j in range(1,m+1):
		for i in range(n):
			totPossible[j] += l[i][j]
	for i in totPossible:
		if(totPossible[i] < x):
			return -1
	combs = []
	for i in range(1,n+1):
		ll = [i for i in range(n)]
		c = list(combinations(ll,i))
		combs.append(c)
	minn = maxsize
	ccc = []
	for i in combs:
		for j in i:
			ccc.append(j)

	for c in ccc:
		ll = [0]*m
		bought = [0]*n
		curr = 0
		for i in c:
			bought[i] = 1
		for i in range(n):
			if(bought[i]):
				for j in range(1,m+1):
					ll[j-1] += l[i][j]
		f = 1
		for i in range(len(ll)):
			if(ll[i] < x):
				f = 0
				break
		if(f):
			for i in range(n):
				if(bought[i]):
					curr += l[i][0]
			minn = min(minn,curr)
	return minn
	

N,M,X = list(map(int, stdin.readline().rstrip().split()))
L = []
for i in range(N):
	l = list(map(int, stdin.readline().rstrip().split()))
	L.append(l)
ans = solve(L,N,M,X)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def list_add(in1, in2):
   return list(map(sum, zip(in1, in2)))

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

n = [i for i in range(N)]
c_sum = 0
min_sum = 12 * 10e5
for i in range(N):
    flag = 0
    for v in itertools.combinations(n,i+1):
        c_sum = 0
        At = [0] * M
        for j in range(len(v)):
            At = list_add(At, A[v[j]])
            c_sum += C[v[j]]
        overX = [k for k in At if k >= X]
        if len(overX) == M:
            flag = 1
            min_sum = min([min_sum, c_sum])
if flag == 1:
    print(min_sum)
else:
    print(-1)

Submission status: Accepted

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

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

ans = 10**7
notFound = True
Nall = 2**N
idx = [0]*N
for num in range(Nall):
    T = num
    for n in range(N):
        idx[n] = T%2
        T = T //2
        
    S = [0]*M
    cost = 0
    for n1 in range(N):
        if idx[n1] == 1:
            a = A[n1]
            cost += A[n1][0]
            for m in range(M):
                S[m] += a[m+1]
            OK = True
            for m in range(M):
                if S[m] < X:
                    OK = False
            if OK:
                ans = min(ans, cost)
                notFound = False
                
                
if notFound:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import collections
import functools

import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, m, x = cin_int_iter()

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

    cnt = collections.Counter()

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

        c[i] = tmp[0]

        for alg, level in enumerate(tmp[1:]):
            a[i][alg] = level

            cnt[alg] += level

    for alg in range(m):
        if cnt[alg] < x:
            print('-1')
            return

    mem = {}

    def search(i, read, levels, cost):
        if all(level >= x for level in levels):
            return cost

        if i == n:
            return float('inf')

        key = (i, read)
        if key in mem:
            return mem[key]

        ret = min(
            search(i + 1, read | 1 << i, [levels[j] + a[i][j] for j in range(m)], cost + c[i]),
            search(i + 1, read, levels, cost)
        )

        mem[key] = ret

        return ret

    print(search(0, 0, [0 for i in range(m)], 0))


main()

Submission status: Accepted

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

import itertools

on_off_list = list(itertools.product([0,1], repeat=n))

dp_c_a = [[0 for i in range(m+1)] for j in range(len(on_off_list))]

# iはパターン、jは参考書、kはアルゴリズム
for i in range(len(on_off_list)):
    for j in range(len(on_off_list[i])):
        for k in range(m+1):
            dp_c_a[i][k] +=  c_a_list[j][k] * on_off_list[i][j]

ans_min = 1000000000
for i in range(len(dp_c_a)):
    count = 0
    for j in range(1, len(dp_c_a[i])):
        if dp_c_a[i][j] < x:
            count += 1
    if count == 0:
        ans_min = min(ans_min, dp_c_a[i][0])

if ans_min == 1000000000:
    print(-1)
else:
    print(ans_min)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().strip().split())
C=[]
A=[]
for n in range(N):
    l=list(map(int,input().strip().split()))
    C.append(l[0])
    A.append(l[1:])

cost=sum(C)
reach=False
def dfs(L,N):
    global reach
    global cost
    if len(L)==N:
        skill=[0 for m in range(M)]
        temp=0
        for n in range(N):
            if L[n]==1:
                temp+=C[n]
                for m in range(M):
                    skill[m]+=A[n][m]
        res=True
        for e in skill:
            if e<X:
                res=False
                break
        
        if res==True:
            reach=True
            if temp<=cost:
                cost=temp     
        return
    
    else:
        for i in range(2):
            L.append(i)
            dfs(L,N)
            L.pop()

dfs([],N)
if reach==True:
    print(cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import math
n, m, x = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(n)] 
CA = np.array(CA)
C = CA[:, 0]
A = CA[:, 1:]
B = np.array([x]*m)

combs = itertools.product(range(2), repeat=n)
opt_val = math.inf
for com in combs:
    X = np.array(com)
    if np.all(A.T @ X >= B):
        opt_val = min(C @ X, opt_val)
if opt_val == math.inf:
    print('-1')
else:
    print(opt_val)

Submission status: Accepted

Solution code:
import copy
n,m,x = map(int,input().split())
ca = [0]*n
for i in range(n):
    ca[i] = list(map(int,input().split()))
ans = 10**8

for i in range(1 << n):
    sum = 0
    result = [0]*m
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in range(m):
                result[k] += ca[j][k+1]
            sum += ca[j][0]
    if min(result) >= x and ans > sum:
        ans = copy.deepcopy(sum)

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

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int, input().split())
books = []
for i in range(N):
    book = list(map(int, input().split()))
    books.append(book)
books = np.array(books)
answer = 10**5 * N
for i in range(2**N):
    flag = False
    bin_str = format(i, '0{}b'.format(N))
    bin_array = []
    for letter in bin_str:
        bin_array.append(int(letter))
    bin_array = np.array(bin_array).reshape(N,1)
    v = np.sum(bin_array*books, axis=0)
    #print(v)
    j = 0
    while j < M:
        if v[j+1] < X:
            break
        j += 1
        if j == M:
            flag = True
            answer = min(answer, v[0])
if flag:
    print(answer)
else:
    print('-1')

Submission status: Accepted

Solution code:
import itertools

def main():
    n,m,x = map(int,input().split())
    c = [[0] * (m+1)]*n
    sum_l = [0]*m
    min_money = 100000000
    money = 0
    cnt = 0
    t = 0

    result  = []

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

    for i in range(1,n+1):
        for conb in itertools.combinations(list(range(n)),i):
            result.append(list(conb))
            cnt += 1

    # print(result)
    # print(cnt)
    for i in range(cnt):
        for j in range(len(result[i])):
            for k in range(m):
                sum_l[k] += c[result[i][j]][k+1]
            money += c[result[i][j]][0]

            for k in range(m):
                if sum_l[k] >= x:
                    t += 1
            if t == m:
                if min_money > money:
                    min_money = money
            t = 0
        # print(result[i],sum_l,money,min_money)
        sum_l = [0]*m
        money = 0

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

    
if __name__ == "__main__":
    main()