Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
info = []
for i in range(n):
    info.append(list(map(int,input().split())))
info = np.array(info)


money = np.sum(info, axis = 0)[0]
flag = 0
for i in range(2**n):
    tem = np.zeros(m+1, dtype = int)
    for j in range(n):
        if ((i >> j) & 1):
            tem += info[j]
    skill = tem[1:]
    non = np.all(skill >= x)
    if non:
        flag = 1
        if tem[0] < money:
            money = tem[0]

if flag == 0:
    print(-1)
else:
    print(money)

Submission status: Accepted

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

# bit = [0 for _ in range(n)]
mincost = 0
cost = 0
learn = [0 for _ in range(n)]
for i in range(n):
	mincost += ca[i][0]

for cnt in range(2**n):
	cost = 0
	learn = [0 for _ in range(m)]

	# bit膳探索
	for i in range(n):
		# bit[i] = (cnt//2**i)%2
		if (cnt//2**i)%2 == 1:
			cost += ca[i][0]
			for j in range(m):
				learn[j] += ca[i][1+j]
	# print(bit)

	# 理解度達成しているか判定
	tassei = True
	for j in range(m):
		if learn[j] < x: tassei = False

	# 達成している and 最小コスト更新している
	if tassei and cost <= mincost:
		mincost = cost
		anytassei = True

if anytassei: print(mincost)
else: print(-1)

Submission status: Accepted

Solution code:
import numpy as np

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

money_list = []
for i in range(1,2 ** n):
    buy_list = []
    money = 0
    for j in range(n):
        if ((i >> j) & 1):
            buy_list.append(understand_list[j])
            money += understand_list[j][0]

    buy_list = np.sum(buy_list, axis=0)
    if all([i >= x for i in buy_list[1:]]):
        money_list.append(buy_list[0])

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

Submission status: Accepted

Solution code:
# C - Skill Up
from itertools import product


def main():
    N, M, X, *CA = map(int, open(0).read().split())
    conditions = tuple(zip(*[iter(CA)] * (M + 1)))
    ans = 1 << 30
    for p in product(range(2), repeat=N):
        cur = [0] * (M + 1)
        for is_available, condition in zip(p, conditions):
            if not is_available:
                continue
            for i, (x, y) in enumerate(zip(cur, condition)):
                cur[i] = x + y
        if all(i >= X for i in cur[1:]):
            ans = min(ans, cur[0])
    print(ans if ans != 1 << 30 else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = []
for i in range(1, 2**n):
    c = [0] * m
    tot = 0
    for j in range(n):
        if ((1<<j) & i):
            for k in range(1, len(a[j])):
                c[k-1] += a[j][k]
            tot += a[j][0]
            poss = 0
            for k in c:
                if k < x:
                    poss = 1
                    break
            if poss == 0:
                ans.append(tot)

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

Submission status: Accepted

Solution code:
n, m ,x = map(int, input().split())
money=[]
understanding = []
min_total = 1000000000000000

for i in range(n):
    inp = list(map(int, input().split()))
    money.append(inp[0])
    understanding.append(inp[1:])

for i in range(2 ** n):
    _sum = 0
    a = [0]*m
    for j in range(n):
        if ((i>>j)&1):
            _sum+=money[j]
            for k in range(m):
                a[k]+=understanding[j][k]
        if min(a)>=x and min_total>=_sum:
            min_total = _sum
if min_total !=1000000000000000:
    print(min_total)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product

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

cost = 10 ** 9
found = False
for bits in product((True, False), repeat=N):
    points = [0] * M
    c = 0
    for index, bit in enumerate(bits):
        if not bit:
            continue

        book = books[index]
        c += book[0]
        for i in range(len(points)):
            points[i] += book[i + 1]

    if all([point >= X for point in points]):
        found = True
        cost = min(cost, c)

if not found:
    cost = -1

print(cost)

Submission status: Accepted

Solution code:
from itertools import combinations

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

cost = 10 ** 9
for r in range(1, N + 1):
    for book_indexes in combinations(range(N), r=r):
        points = [0] * M
        c = 0
        for index in book_indexes:
            book = books[index]
            c += book[0]
            for i in range(len(points)):
                points[i] += book[i + 1]
        if all([point >= X for point in points]):
            cost = min(cost, c)

if cost == 10 ** 9:
    cost = -1
print(cost)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
li = [list(map(int,input().split())) for i in range(N)]
ans = 10**9

for i in range(2**N):#bit全探索
    case = []
    for j in range(N):
        if ((i >> j) & 1):
            case.append(li[j])
    result = [sum(list(map(lambda x:x[i], case))) for i in range(1,M+1)]
    if min(result)>=X:
        ans = min(ans,sum(list(map(lambda x:x[0], case))))

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)]
result=[]
result_2=[]
for bit in range(1 << n):
  book_add=[0 for _ in range(m+1)]
  for i in range(n):
    if (bit >> i) & 1:
      book_add=[x+y for x,y in zip(book_add,a[i])]
  temporary_list=[]
  for j in range(1,m+1):
    if book_add[j]>=x:
      temporary_list.append(book_add[j])
  if len(temporary_list)==m:
    result.append(book_add)
if len(result)==0:
   print(-1)
else:
  for k in range(len(result)):
    result_2.append(result[k][0])
  print(min(result_2))

Submission status: Accepted

Solution code:
book_num, arg_num, dest = map(int, input().split(" "))
Cs = []
As = []
ans = []
for _ in range(book_num):
    li = list(map(int, input().split(" ")))
    Cs.append(li[0])
    As.append(li[1:])
for i in range(2 ** book_num):
    ja = [0]*arg_num
    cost = 0
    for j in range(book_num):
        if ((i >> j) & 1):
            for s in range(arg_num):
                ja[s] += As[j][s]
            cost += Cs[j]
    flag = 0
    for j in ja:
        if j < dest:
            flag = 1
    if flag == 0:
        ans.append(cost)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
cost = []
text = []
ans = 12 * 10**5
find = False

for _ in range(N):
    C, *A = map(int, input().split())
    cost.append(C)
    text.append(A)

for i in range(2**N):
    yen = 0
    understand = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            yen += cost[j]
            for k in range(M):
                understand[k] += text[j][k]
    
    if all([u >= X for u in understand]):
        ans = min(ans, yen)
        find = True

print(ans if find else -1)

Submission status: Accepted

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

ans=sum(c)+1
for i in range(2**n):
  rikaido=[0]*m
  money=0
  for j in range(n):
    if ((i>>j)&1):
      money+=c[j]
      for k in range(m):
        rikaido[k]+=a[j][k]
  for k in range(m):
    if rikaido[k]<x:
      break
  else:
    if money<ans:
      ans=money

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
c= []
a= []
ans = float('inf')
for i in range(n):
    c_tmp, *a_tmp = map(int, input().split())
    c.append(c_tmp)
    a.append(a_tmp)


cost_l =[]

for i in range(2 ** len(c)):
    cost = 0
    skill = [0]*m
    for j in range(len(c)):  
        if ((i >> j) & 1):
            cost += c[j]
            for k in range(m):
                skill[k] += int(a[j][k])
    
    f = 0
    for j in range(m):
        if skill[j] < x:
            f = 1
            break
    if f == 0:
        cost_l.append(cost)
            
if cost_l != []:
    print(min(cost_l))
else:
    print("-1")

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10**8)

def dfs(i,a,value):
  global ans
  if i==n:
    if all(a[i]>=x for i in range(m)):
      ans=min(ans,value)


  else:
    dfs(i+1,a,value)
    dfs(i+1,a+np.array(pc[i][1:]),value+pc[i][0])


ans=float('inf')
n,m,x=map(int,input().split())
pc=[]
for i in range(n):
  s=list(map(int,input().split()))
  pc.append(s)

dfs(0,np.array([0]*(m)),0)
if ans==float('inf'):
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X=map(int,input().split())
C,A=[],[]
min=10000000
for i in range(N):
  A.append(list(map(int,input().split())))
A=np.matrix(A)
for i in range(2**N):
  NP=np.matrix(list(map(int,list(format(i,'b').zfill(N)))))
  result=np.dot(NP,A)
  if np.all(result[0,1:]>=X):
    if min>result[0,0]:
      min=result[0,0]
if min==10000000:
  min=-1
print(min)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = (int(i) for i in input().split())  
c = [[int(i) for i in input().split()] for i in range(N)] 
c = np.array(c)
cost = 12*10**5*10
cmp_flg = False
for i in range(2**N):
  m = np.zeros(M)
  tmp_cost = 0
  for j in range(N):
    if ((i>>j)&1):
      m += c[j][1:]
      tmp_cost += c[j][0]
  if (min(m)>=X) & (tmp_cost<cost):
    cmp_flg = True
    cost = tmp_cost
    
if cmp_flg ==True:
  print(cost)
else:
  print("-1")

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans = 10 ** 5 * 12
kai = False
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        if np.all(arr_i2_sum[1:] >= X):
            if ans >= arr_i2_sum[0]:
                ans = arr_i2_sum[0]
                kai = True
if kai:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def resolve():
	n, m, x = map(int, input().split())
	c_seq = []
	a_seq = []
	ans = float('inf')
	for i in range(n):
		c, *a = map(int, input().split())
		c_seq.append(c)
		a_seq.append(a)
	for i in range(1 << n):
		pay = 0
		skill = [0]*m
		for j in range(n):
			if i >> j & 1:
				pay += c_seq[j]
				for k in range(m):
					skill[k] += a_seq[j][k]
		ok = True
		for y in skill:
			if x > y:
				ok = False
		if ok:
			ans = min(ans, pay)
	print(ans if ans < float('inf') else -1)
resolve()

Submission status: Accepted

Solution code:
import sys
N, M, X=map(int, sys.stdin.readline().rstrip().split())
A = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(N)]
cost=[]
for i in range(1<<N):	#Bit All Search
	l=[0]*(M+1)			#Initialize Check list
	for j in range(N):
		if((i>>j)&1):	#delete ==1
			l=[l[k]+A[j][k] for k in range(M+1)]
	for k in range(M):
		if l[k+1]<X:
			break
	else:cost.append(l[0])
cost.sort()
print(-1 if cost==[] else cost[0])

Submission status: Accepted

Solution code:
import sys
N, M, X=map(int, sys.stdin.readline().rstrip().split())
A = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(N)]
cost=[]
for i in range(1<<N):	#Bit All Search
	l=[0]*(M+1)
	for j in range(N):
		if((i>>j)&1)==1:
			l=[l[k]+A[j][k] for k in range(M+1)]
	for k in range(M):
		if l[k+1]<X:
			break
	else:
		cost.append(l[0])
cost.sort()
print(-1 if cost==[] else cost[0])

Submission status: Accepted

Solution code:
from operator import add
n,m,x = map(int, input().split())
#n: 参考書の数, m: 学びたいアルゴリズムの数, x: 達成したい理解度
C = []
A = []
for _ in range(n):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)

ans = 10**10
flg = False
for bit in range(2**n):
    tmp = 0
    tmp_list=[0]*m
    for j in range(n):
        if (bit >> j) & 1:
            tmp += C[j]
            tmp_list = map(add, tmp_list, A[j])
    if min(tmp_list) >= x: #目標を達成
        ans = min(ans, tmp)
        flg = True

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

Submission status: Accepted

Solution code:
import sys
N, M, X=map(int, sys.stdin.readline().rstrip().split())
A = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(N)]
cost=[]
for i in range(1<<N):	#Bit All Search
	l=[0]*(M+1)
	for j in range(N):
		if((i>>j)&1)==1:
			l=[l[k]+A[j][k] for k in range(M+1)]
	for k in range(M):
		if l[k+1]<X:
			break
	else:
		cost.append(l[0])
cost.sort()
print(-1 if cost==[] else cost[0])

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

# input
N, M, X = LI()
C, A = [None] * N, [None] * N
for i in range(N):
    C[i], *A[i] = list(map(int, input().split()))

INF = 10 ** 10

H = []
L = [i for i in range(N)]
for i in range(1, N + 1):
    H += ((list(itertools.combinations(L, i))))

ans = INF
for h in H:
    cost = 0
    a = [0] * M
    for v in h:
        cost += C[v]
        for i in range(M):
            a[i] += A[v][i]
    b = True
    for i in range(M):
        if a[i] < X:
            b = False
            break
    if b == True: # if b:と同義
        ans = min(cost, ans)
if ans == INF:
    print("-1")
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
book=[]
mon=[]
ans=0
for i in range(n):
      cnt=list(map(int,input().split()))
      mon.append(cnt[0])
      book.append(cnt[1:])
min_total=100000000000000
for i in range(2**n):
        a=[0]*m
        total=0
        for j in range(n):
                if ((i >>j)&1):
                        total+=mon[j]
                        for k in range(m):
                                a[k]+=book[j][k]
                if min(a) >=x and min_total>=total:
                        min_total=total
if min_total!=100000000000000:
        print(min_total)
else:
        print('-1')

Submission status: Accepted

Solution code:
#167C bit探索
def main():
    import sys, numpy as np
    
    N,M,X =map(int, sys.stdin.readline().split())
    CAB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    
    #bit探索
    ans = -1
    for i in range(2**N):
        result = np.array([0 for _ in range(M+1)])
        for j in range(N): #桁(右始まり)
            if ((i>>j) &1) ==1:
                result +=np.array(CAB[N-j-1])
        if np.all(result[1:]>=X):
            if ans==-1 or ans > result[0]:
                ans = result[0]
    print(ans)
   

if __name__=='__main__':
    main()

Submission status: Accepted

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

money=[]
for i in range(2**N):
    K=[]
    for l in range(M):
        K.append(0)
    total=0
    for k in range(N):
        if (i>>k)&1==1:
            for j in range(1,M+1):
                K[j-1]+=C[k][j]
            total+=C[k][0]
    if min(K)>=X:
        money.append(total)
try:
    print(min(money))
except:
    print(-1)

Submission status: Accepted

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

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


for i in range(N):
    tmp = input().split()
    c[i] = int(tmp[0])
    for l in range(M):
        a[i][l] = int(tmp[l+1])

Pattern = 2**(N)
TotalOld = 1<<60 
Flag = False

for i in range(Pattern):
    Total = 0
    learn = [0]*M
    for b in range(N):
        if (i>>b)&1 == 1:
            Total += c[b]
            for m in range(0,M):
                learn[m] += a[b][m]
    if min(learn) >= X and Total < TotalOld:
        TotalOld = Total
        Flag = True

if Flag:
    print(TotalOld)
else:
    print('-1')

Submission status: Accepted

Solution code:
#　N：スキル数、M:本の数、X：達成したい習熟度
N,M,X=list(map(int,input().split()))
A =[]
C =[]
for n in range(N):
    input_temp=list(map(int,input().split()))
    C.append(input_temp[0])
    A.append(input_temp[1:])

def get_sum_list(bag):
    sum_list=[0]*M
    for b in bag:
        sum_list=[a + b for a, b in zip(sum_list,b)]
    return sum_list

#各本を買うかをbit全探索
ans = []
for n in range(2**N):
    bag = []
    charge = 0
    for j in range(N):
        if ((n >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(A[j]) 
            charge += C[j]
    sum_list=get_sum_list(bag)
    
    if min(sum_list) >= X:
        ans.append(charge)
        
#     print(bag,sum_list,ans)
    
if len(ans)>0:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

num_of_books, num_of_algorithm, understanding = map(int, input().split())

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

mincost = -1
# 本1冊に対して買う買わないの2値があるため、2の冊数乗回ループ(bit全探索)
for i in range(2 ** num_of_books):

    # 購入する本のリスト
    bag = []
    totalcost = 0

    # 10進数iを購入のbitパターンとしたときのループ
    for j in range(num_of_books):
        # ビットを指定桁だけ右にシフトし、最下位ビット（購入の有無）をチェック
        # 1(0…1)と論理積を取ることで最下位ビットを確認できる
        if((i >> j) & 1):
            bag.append(books[j][1:])
            totalcost = totalcost + books[j][0]
        
    # すべての理解度が基準を超えているか
    # 購入した本の理解度の合計を算出し、すべて基準値以上か
    # (np.allで要素がすべてtrueか)
    if np.all(np.sum(np.array(bag), axis=0) >= understanding):
        if mincost == -1 or totalcost < mincost:
            mincost = totalcost 

print(mincost)

Submission status: Accepted

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

N,M,X = map(int,input().rstrip().split())
C = []
A = []
for i in range(N):
    c, *a = [int(i) for i in input().rstrip().split()]
    C.append(c)
    A.append(a)

ans = 10**18
for i in range(2**N):
    d = [0]*M
    cst = 0
    for j in range(N):
        if (i>>j&1):
            cst += C[j]
            for s in range(M):
                d[s] += A[j][s]

    for j in d:
        if j < X:
            break
    else:
        ans = min(ans,cst)

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

Submission status: Accepted

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

N,M,X = map(int,input().rstrip().split())
C = []
A = []
for i in range(N):
    c, *a = [int(i) for i in input().rstrip().split()]
    C.append(c)
    A.append(a)

ans = 10**18
for i in range(2**N):
    d = [0]*M
    cst = 0
    for j in range(N):
        if (i>>j&1):
            cst += C[j]
            for s in range(M):
                d[s] += A[j][s]
    ok = True
    for j in d:
        if j < X:
            ok = False

    if(ok):
        ans = min(ans,cst)

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

Submission status: Accepted

Solution code:
def main():
    n, m, x = [int(x) for x in input().split()]
    prices = [None] * n
    contents = [None] * n
    for book_i in range(n):
        price, *content_in_a_manual = [int(x) for x in input().split()]
        prices[book_i] = price
        contents[book_i] = content_in_a_manual
    INF = 10 ** 9
    ans = INF
    for num in range(1 << n):
        payment = 0
        understanding = [0] * m
        for book_i in range(n):
            if num >> book_i & 1:
                payment += prices[book_i]
                for algo_i, value in enumerate(contents[book_i]):
                    understanding[algo_i] += value
        if min(understanding) >= x:
            ans = min(ans, payment)
    if ans == INF:
        return - 1
    else:
        return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N,M,X = LI()
B = [LI() for _ in range(N)]
C = []
A = []
S = [0] * M

for ind,b in enumerate(B):
	C.append(b[0])
	A.append(b[1:])
	for i,v in enumerate(b[1:]):
		S[i]+=v

for s in S:
	if s < X:
		print("-1")
		exit(0)

def bit_all():
	minmoney = 10**7
	bit = 0
	while bit < 2**N:
		T = [X] * M
		now = 0
		#print(bit)
		for i in range(N):
			#print("\t",i)
			flg = True
			if ((bit >> i)&1):
				for ind in range(M):
					T[ind]-=A[i][ind]
					if T[ind] > 0:
						flg = False
				now+=C[i]
				if flg:
					#print(now)
					if now < minmoney:
						minmoney = now
					break
		bit+=1
	return minmoney

print(bit_all())

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

maxnum = 10000000000
def dfs(a,cost,i):
    if min(a) >= x:
        return cost
    elif i == n:
        return maxnum
    
    getA = [x+y for (x,y) in zip(a,A[i])]
    
    return min(dfs(a,cost,i+1), dfs(getA,cost+C[i],i+1))

ans = dfs([0]*m,0,0)

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

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n, m, x = nm()
    arr = []
    for _ in range(n):
        temp = nl()
        arr.append(temp)

    costs = []
    for i in range(2**n):
        binary = bin(i)[2:]
        binary = '0'*(n-len(binary)) + binary
        count = [0]*m
        cost = 0
        for i, num in enumerate(binary):
            if num == '1':
                for j in range(m):
                    count[j] += arr[i][j+1]
                cost += arr[i][0]
        #print(binary, cost)
        flag = True
        for value in count:
            if value < x:
                flag = False
        if flag:
            costs.append(cost)
    if costs == []:
        print(-1)
    else:
        print(min(costs))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
li=[input() for i in range(n)]
li2 = []
for i in range(n):
    li2.append( [int(x.strip()) for x in li[i].split()])
    
ans = 10**7

for i in range(2 ** n):
    res = ""
    b = str(format(i, '012b')) #2進数に変換
    a = [0]*(m+1)
    for j in range(n):
        if b[-1-j] == "1":
            a = [x1 + x2 for (x1, x2) in zip(a, li2[j])]
           # print(a)
            
    c = len([j for j in a[1:] if j>=x])
    if c ==m and ans>a[0]:
        
        ans = a[0]
        #print(ans)

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

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
c = []
a = []
for i in range(N):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])
c = np.array(c)
a = np.array(a)
min_money = 10 ** 8
flag = False
for i in range(2 ** N):
    order = []
    for j in range(N):
        if (i >> j) & 1:
            order.append(j)
    if not len(order):
        continue
    rikaido = np.sum(a[np.array(order)], axis=0)
    if np.all(rikaido >= X):
        flag = True
        money = np.sum(c[order])
        if min_money > money:
            min_money = money
if flag:
    print(min_money)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = []
A = []
ans = 12*(10**5)+1
for _ in range(N):
    tmp = list(map(int,input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])
#print(C)
#print(A)

for i in range(2**N):
    knowledge = [0]*M
    cost = 0
    for j in range(N):
        if (i>>j) & 1: # bit全探索
            cost += C[j]
            for k in range(M):
                knowledge[k] += A[j][k]
    if min(knowledge) >= X:
        ans = min(ans,cost)
if ans == 12*(10**5)+1:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
ans = 12*(10**5)+1
for _ in range(n):
    ca = list(map(int,input().split()))
    c.append(ca[0])
    a.append(ca[1:])

for i in range(2**n):
    l = [0]*m
    cost = 0
    for j in range(n):
        if (i>>j)&1:
            cost += c[j]
            for k in range(m):
                l[k] += a[j][k]
    if min(l)>=x:
        ans = min(cost,ans)
if ans == 12*(10**5)+1:
    ans = -1
print(ans)

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 = float('inf')
for i in range(2**N):
    Level = [0]* M
    Cost = 0
    
    for j in range(N):
        if (i>>j)&1:
            Cost += C[j]
            for k in range(M):
                Level[k] += A[j][k]
                
    if all([Level[l] >= X for l in range(M)]):
        ans = min(ans, Cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ans = 12*(10**5)+1
C = []
A = []

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

for i in range(2**n):
    understood = [0]*m
    cost = 0
    
    for j in range(n):
        if (i>>j)&1:
            cost += C[j]
            
            for k in range(m):
                understood[k] += A[j][k]
            
    if min(understood) >= x:
        ans = min(ans,cost)

if ans == 12*(10**5)+1:
    ans = -1
        
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ans = 12*(10**5)+1
C = []
A = []

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

for i in range(2**n):
    understood = [0]*m
    cost = 0
    
    for j in range(n):
        if (i>>j)&1:
            cost += C[j]
            
            for k in range(m):
                understood[k] += A[j][k]
                
    ok = 0
        
    for j in understood:
        if j >= x:
            ok += 1
            
    if ok == m:
        ans = min(ans,cost)

if ans == 12*(10**5)+1:
    ans = -1
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in product([0,1],repeat=n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if i[j]:
            #(✳︎)
            ans_+=ca[j][0]
            for k in range(m):
                check[k]+=ca[j][k+1]
    if all([l>=x for l in check]):
        ans=min(ans,ans_)
if ans==100000000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

for i in range(2**N):
    cnt = [0] * M
    c = 0
    idx = 0
    while i:
        if i % 2:
            c += A[idx][0]
            for j in range(1, M+1):
                cnt[j-1] += A[idx][j]
        idx += 1
        i //= 2
        
    for j in cnt:
        if j < X: break
    else: ans = min(ans, c)
    
if ans == float('inf'): ans = -1
print(ans)

Submission status: Accepted

Solution code:
def check(pair,m,x):
  sum = 0
  
  for i in range(1,m+1):
    p= 0
    for e in pair:
      p += e[i]
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
  sum = check(pair,m,x)
  
  if min == -1:
    min = sum
  elif sum != -1 and min > sum:
    min = sum
    
print(min)

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split(' '))
matrix = np.array([list(map(int, input().split(' ')))  for i in range(N)])
price = []
for i in range(2**N):
    res = np.zeros(M+1)
    for j in range(N):
        if ((i >> j) & 1):
            res += matrix[j]
        if res[1:].min() >=X:
            price.append(res[0])
price = np.array(price)
if len(price) > 0:
    print(int(price.min()))
else:
    print('-1')

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ans = 12*(10**5)+1
C = []
A = []

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

for i in range(2**n):
    understood = [0]*m
    cost = 0
    
    for j in range(n):
        if (i>>j)&1:
            cost += C[j]
            
            for k in range(m):
                understood[k] += A[j][k]
                
    ok = 0
        
    for j in understood:
        if j >= x:
            ok += 1
            
    if ok == m:
        ans = min(ans,cost)

if ans == 12*(10**5)+1:
    ans = -1
        
print(ans)