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())
ca = [list(map(int, input().split())) for _ in range(n)]
ans = float("inf")
for i in range(2**n):
    flag = True
    achive = [0]*m
    cost = 0
    for j in range(n):
        if i >> j & 1 == 1:
            cost += ca[j][0]
            for k in range(m):
                achive[k] += ca[j][k+1]

    for item in achive:
        if item < x:
            flag = False
    if flag:
        ans = min(ans, cost)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
a = input().split(" ")
x = int(a[2])
m = int(a[1])
n = int(a[0])
s= []
p = [] 
for i in range(n):
  aa = input().split(" ")
  ss = []
  for ii in aa:
    ss.append(int(ii))
  s.append(ss[1:])
  p.append(ss[0])
    
from itertools import chain, combinations
def getPrice(indexes):
  t = 0
  for i in indexes:
    t += p[i]
  return t
def doesSatisfy(indexes):
  t = 0
  alg_totals = [0] * m
  for i in indexes:
    for ii in range(m):
      alg_totals[ii] += s[i][ii]
  for i in alg_totals:
    if i < x:
      return False
  return True

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

  
lowest = -1  
for i in list(powerset(list(range(n)))):
  price = getPrice(i)
  if doesSatisfy(i) and lowest == -1:
    lowest = price
  elif doesSatisfy(i) and price < lowest:
    lowest = price

print(lowest)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N, M, K = map(int, input().split())
Q = [np.asarray(input().split(), dtype=int) for i in range(N)]
min_cost = 10**9
def dfs(cost, C, depth=0):
  global min_cost
  if (C >= K).all():
    min_cost = min([cost, min_cost])
    return
  if depth == N:
    return
  dfs(cost+Q[depth][0], C + Q[depth][1:], depth+1)
  dfs(cost, C, depth+1)
  
dfs(0, np.zeros(M))
    
print(min_cost) if min_cost != 10**9 else print(-1)

Submission status: Accepted

Solution code:
import itertools

p = list(map(int,input().split()))
N = p[0]
M = p[1]
X = p[2]

l = [[int(i) for i in input().split()] for j in range(N)]
l_a = []
k_1 = list(range(1,N+1))
for i in itertools.combinations_with_replacement(k_1, N):
    l_a.append(list(set(i)))
l_a = list(map(list, set(map(tuple, l_a))))
l_v = float('inf')
f_1 = False
for ls in l_a:
    ls = list(set(ls))
    ans = [0] * M
    val = 0
    for a in ls:# a = [1,2]ながさM
        for ix,i in enumerate(l[a-1][1:]):
            ans[ix] += i
        val += l[a-1][0]
    b = [i for i in ans if i >= X]
    if len(b) == len(ans):
        l_v = min(l_v, val)
        f_1 = True
if f_1:
    print(l_v)
else:
    print(-1)

Submission status: Accepted

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

bookli = [[0 for I in range(M+1)] for II in range(N)]
for i in range(N):
    bookli[i] = list(map(int, input().split()))

ans=10**9

for j in range(1, 2**N):
    ansli = [0 for III in range(M+1)]
    keta = N
    for jj in range(keta):
        if ((j >> jj) & 1):
            ansli = [a + b for (a, b) in zip(ansli, bookli[jj])]

    for k in range(1, M+1):
        if ansli[k] >= X:
            pass
        else:
            break

        if k==M and ans > ansli[0]:
            ans=ansli[0]



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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M, X = MAP()

    C, A = [], []
    for i in range(N):
        c, *a = MAP()
        C.append(c)
        A.append(a)

    ans = INF
    for tup in list(product(range(2), repeat=N)):
        temp = [0 for _ in range(M)]

        for i in range(N):
            for j in range(M):
                if tup[i]:
                    temp[j] += A[i][j]

        flag = True
        for j in range(M):
            if temp[j] < X: flag = False

        if flag:
            money = 0
            for i in range(N):
                money += C[i] * tup[i]

            ans = min(money, ans)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

costs=[]

for i in range(2**n):
    t=[0]*m
    cost=0
    for j in range(n):
        if ((i>>j)&1)==1:
            for k in range(m):
                t[k]+=book[j][k+1]
            cost+=book[j][0]
        
    if all(t[l]>=x for l in range(m)):
        costs.append(cost)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

C_list = []
A_list = []

for i in range(N):
    inp = list(map(int, input().rstrip().split()))
    C_list.append(inp[0])
    A_list.append(inp[1:])
#-----

bit = 1 << N
max_price = sum(C_list)*2
min_price = max_price

for b in range(bit):
    price = 0
    study = [0]*M
    
    for i in range(N):
        if (b & (1 << i)):
            price += C_list[i]
            
            for j in range(len(A_list[i])):
                study[j] += A_list[i][j]
    
    if min(study) >= X:
        min_price = min(min_price, price)


print(min_price if min_price != max_price else -1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for i in range(N)]
CA = np.array(CA)
# print(CA)

C = [CA[i][0] for i in range(N)]
# print(C)
min_ans = 10**7

l = range(N)

for i in range(N):
    c = list(itertools.combinations(l, i+1))
    for j in range(len(c)):
        # print(c[j])
        target_book = np.array([CA[a] for a in c[j]])
        rikai = np.sum(target_book,axis=0)
        # print(rikai[1:])
        # print(target_book)
        # print(rikai)

        if min(rikai[1:]) >= X and min_ans > rikai[0]:
            # print(rikai[1:])
            # print(target_book)
            # print(rikai)
            min_ans = rikai[0]

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def ii(v, n):
	v += 2 ** 15
	ret = bin(v)[-n:]
	#ret = ret[::-1]
	return ret

def vs(a,b):
	return [va+vb for va,vb in zip(a, b)]

def main():
	#a = int(input())
	n, m, x = IN()
	#s = input()
	bb = []
	for _ in range(n):
		dd = LIN()
		bb.append(dd)
	
	min_c = mod
	for i in range(2 ** n):
		c = 0
		mm = [0]*m
		rr = ii(i, n)
		for ik, keta in enumerate(rr):
			if keta == '1':
				l= bb[ik]
				c += l[0]
				mm = vs(mm, l[1:])
		if min(mm) >= x and c < min_c:
			min_c = c
	if min_c < mod:
		return min_c
	else:
		return -1
				
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
N, M, X=map(int,input().split())
A=[[0 for k in range(M+1)] for k in range(N)]
for k in range(N):
    A[k] = list(map(int, input().split()))

possible=[]


for k in range(2**N):
    bit = str(bin(k))
    count = 0
    howmuch = 0

    for l in range(1, M+1):
        for j in range(1, len(bit)-1):
            if bit[-j] == "1":
                count += A[j-1][l]
    
        if count < X:
            break
        count = 0
        

    else:
        for j in range(1, len(bit)-1):
            if bit[-j] == "1":
                howmuch += A[j-1][0]
        possible.append(howmuch)
if len(possible)>0:
    print(min(possible))
else:
    print(-1)

Submission status: Accepted

Solution code:
from operator import add

n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(n)]
cost = []
for i in range(2 ** n):
  total = 0
  algo = [0] * m
  for j in range(n):
    if ((i >> j) & 1):
      algo = map(add, algo, books[j][1::])
      total += books[j][0]

  count = 0
  for k in algo:
    if k >= x:
      count += 1
  
  if count == m:
    cost.append(total)

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

Submission status: Accepted

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

for i in range(1,2**(N+1)):
  bought = list(format(i, '0{}b'.format(N)))
  params = [0] * (M+1)
  for b, book in zip(bought, books):
    if b == '1':
      params = [pi+ai for pi,ai in zip(params,book)]
  for p in params[1:]:
    if p < X:
      break
  else:
    buy.append(params)

buy.sort()
print(buy[0][0] if len(buy) > 0 else -1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

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

ans = []
for k in range(1,N+1):
  rows = list(itertools.combinations(list(range(N)),k))
  for row in rows:
    Crow = 0
    Arow = np.array([0]*M)
    for j in range(len(row)):
      Crow += C[row[j]]
      Arow += np.array(A[row[j]])
    if all(a >=X for a in Arow):
      ans.append(Crow)
if len(ans) == 0:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import numpy as np
    n,m,x=map(int, input().split())
    l=[list(map(int,input().split())) for i in range(n)]
    kanel=[]
    for i in range(2 ** n):
        kaul = np.array([0] * (m+1))
        for j in range(n): 
            if ((i >> j) & 1):  
                l[j]=np.array(l[j])
                kaul=kaul+l[j]
        flag=True
        for k in kaul[1:]:
            if k<x:
                flag = False
                break

        if flag:
            kanel.append(kaul[0])
    if kanel==[]:
        print(-1)
    else:
        print(min(kanel))
resolve()

Submission status: Accepted

Solution code:
from itertools import combinations

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

caa_list = []

for i in range(n):
  c, *aa = map(int, input().strip().split())
  caa_list.append((c, aa))

caa_list.sort(key=lambda x: x[0])

mc = 10 ** 9

for i in range(1, n+1):
  for caas in combinations(caa_list, i):
    sc = 0
    saa = [0] * m
    for c, aa in caas:
      sc += c
      for j in range(m):
        saa[j] += aa[j]
    if all(a >= x for a in saa):
      if mc > sc:
        mc = sc
        
if mc == 10 ** 9:
  print(-1)
else:
  print(mc)

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
_mt = [list(map(int, input().split())) for _ in range(n)]
cs = [r[0] for r in _mt]
anm = [r[1:] for r in _mt]

sumlst = lambda l1, l2: [i1+i2 for i1, i2 in zip(l1, l2)]

mat = [{} for _ in range(n + 1)]
mat[0][0] = (0, [0]*m)
for i in range(n):
    for j in mat[i]:
        w, seq = mat[i][j]
        # Ciを採用しなかった場合
        mat[i + 1][w] = (w, seq)
        # Ciを採用した場合
        mat[i + 1][w + cs[i]] = (w + cs[i], sumlst(seq, anm[i]))

for k in sorted(mat[-1]):
    w, lst = mat[-1][k]
    if all(v >= x for v in lst):
        print(w)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
import math
INF = float('inf')

def rec(k,und,ans):
	#print(k,ans)
	if(k==N):
		if(sum(und >= X) == len(und)):
			return ans
		else:
			return INF
	else:
		return min(rec(k+1,und+CA[k][1:],ans+CA[k][0]),rec(k+1,und,ans))	


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

CA = [[None for i in range(M+1)] for j in range(N)] 
for i in range(N):
	CA[i] = list(map(int,input().split()))


und =  np.array([0 for i in range(M)])	
ans = rec(0,und,0)
print(-1 if ans==INF else ans)

Submission status: Accepted

Solution code:






def     process(tab, tour, current, result,skill, N, M, X):
    finish = True
    for i in skill:
        if (i < X):
            finish = False
            break
    if (finish):
        if (result == -1):
            return current
        else:
            return min(result, current)
    if (tour == N or (current > result and result > -1)):
        return result

    current += tab[tour][0]
    for i in range(1, M+1):
        skill[i-1] += tab[tour][i]
    avec = process(tab, tour + 1, current, result, skill, N, M, X)
    
    if (result == -1 or (avec < result and avec > -1)):
        result = avec
    current -= tab[tour][0]
    for i in range(1, M+1):
        skill[i-1] -= tab[tour][i]
    sans = process(tab, tour + 1, current, result, skill, N, M, X)
    
    if (result == -1 or (sans < result and sans > -1)):
        result = sans
    return result


data = input().split()
n,m,x = int(data[0]), int(data[1]), int(data[2])


tab = []
for i in range (n):
    data = input().split()
    t = []
    for j in range (m+1):
        t.append(int(data[j]))
    tab.append(t)


skill = [0] * m
result = process(tab, 0, 0, -1, skill, n,m,x)
print(result)

Submission status: Accepted

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

minv = np.inf
zeros = np.zeros(M+1)

for i in range(2**N):
    tmp = zeros.copy()
    for j in range(N):
        if (i >> j) & 1:
            tmp += datas[j]
            if np.all(tmp[1:len(tmp)] >= X):
                c = np.sum(tmp.T[0])
                if c < minv:
                    minv = c
                break
ret = int(minv) if minv != np.inf else -1
print(ret)

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
a = [list(map(int, input().split())) for i in range(N)]
li = []
for i in range(N+1):
    for j in itertools.combinations(range(N), i):
        sm = [0] * (M+1)
        for k in j:
            for l in range(M+1):
                sm[l] += a[k][l]
        if all(y >= X for y in sm[1:M+1]):
            li.append(sm[0])
if li == []:
    print(-1)
else:
    print(min(li))

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
a=[]
ans=-1
for _ in range(N):
    A=list(map(int,input().split()))
    a.append(A)
for i in range(2**N):
    skill=[0]*(M)
    flag=0
    money=0
    for j in range(N):
        if ((i>>j)&1):
            money+=a[j][0]
            for k in range(1,M+1):
                skill[k-1]+=a[j][k]
    for l in skill:
        if l<K:
            flag=1
            break
    if flag==0:
        if ans==-1:
            ans=money
        else:
            ans=min(money,ans)
print(ans)

Submission status: Accepted

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

C_list = [list(map(int, input().split())) for i in range(N)]
import itertools

targets = list(itertools.product([0, 1], repeat=N))
#print(targets)
answer = 10 ** 9
for target in targets:
    result = [0] * (M + 1)
    for i, t in enumerate(target):
        if t == 1:
            for j in range(M + 1):
                result[j] += C_list[i][j]
        #print(result)
    if min(result[1:]) >= X:
        #print(result)
        answer = min(answer,result[0])
if answer == 10 ** 9:
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
import itertools

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

ans_list_ = []

origin_list = data
for i, _ in enumerate(origin_list, 1):     
  for j in itertools.combinations(origin_list, r=i):  # rには1、2、3と渡される
    # print(list(j))

    # 合計値リスト
    each_point_list_ = [0] * m
    for j_ in j:
      for m_ in range(m):
        each_point_list_[m_] += j_[m_+1]

    # X判定
    flag_ = True
    for epl in each_point_list_:
      if epl < x:
        flag_ = False
    
    if flag_:
      # 金額の計算
      price_ = 0
      for j_ in j:
        price_ += j_[0]
      
      ans_list_.append( price_ )

    # print(*each_point_list_)

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

Submission status: Accepted

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

ans = [10**9]
index = 0
score = [0]*M
coin = 0
import copy

def rec(index,coin,score):
    # print(score,index)
    if index > N-1:
        f = True
        for i in range(M):
            if score[i] < X:
                f = False
        if f:
            # print(score)
            # print(score)
            ans[0] = min(ans[0],coin)

        return 1
    
    
    # rec(index+1,coin,score)
    score1 = copy.deepcopy(score)
    rec(index+1,coin,score1)

    for i in range(M):
        score1[i] += C[index][i+1]
    # print("a")
    # print(score1,C[index])
    rec(index+1,coin+C[index][0],score1)
    # print("b")
    return 1


rec(index,coin,score)

if ans[0]==10**9:
    ans[0] = -1
print(ans[0])

Submission status: Accepted

Solution code:
import itertools
#import pprint
N, M, X = map(int, input().split())
C = []
for i in range(N):
    C.append(list(map(int, input().split())))
choice = list(itertools.product([False, True], repeat = N))
#pprint.pprint(choice)
best = False
for i in choice:
    cost = 0
    now = [0 for j in range(M)]
    flag = True
    for j in range(N):
        if i[j]:
            cost += C[j][0]
            now = [now[k] + C[j][k + 1] for k in range(M)]
    for j in now:
        if j < X:
            flag = False
#    print(i, now, cost)
    if flag:
        if best == False:
            best = cost
        elif best > cost:
            best = cost
if best == False:
    print(-1)
else:
    print(best)

Submission status: Accepted

Solution code:
from itertools import combinations
I=lambda:list(map(int,input().split()))
n,m,x=I()
rec=[]
for i in range(n):
  rec.append(I())
best=10**9
for i in range(1,n+1):
  l=list(combinations(rec,i))
  #print(l)
  for j in range(len(l)):
    loc_best=0
    algos=[0 for _ in range(m+1)]
    for k in range(len(l[j])):
      loc_best+=l[j][k][0]
      for p in range(1,m+1):
        algos[p]+=l[j][k][p]
    #print(loc_best,algos)
    st=False
    for p in range(1,m+1):
      if(algos[p]<x):
        st=True
        break
    if(st==False):
      best=min(loc_best,best)
if(best==10**9):
  print(-1)
else:
  print(best)

Submission status: Accepted

Solution code:
import itertools as itt

n,m,x = map(int, input().split())
lsts = []
cbs = []
minp = -1

for i in range(n):
  lsts.append(input().split())
  for j in range(m+1):
    lsts[i][j] = int(lsts[i][j])
#

for i in range(1,n+1):
  cbs += list(itt.combinations(lsts,i))
#print(cbs)

for i in range(len(cbs)):
  p = 0
  algs = [0]*m
  flg = True
  for j in range(len(cbs[i])):
    p += cbs[i][j][0]
    for k in range(m):
      algs[k] += cbs[i][j][k+1]
  for alg in algs:
    if alg < x:
      flg = False
  if flg and (minp == -1 or p < minp):
    minp = p
#

print(minp)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
N, M, X = map(int, input().split())

mylist = []

for n in range(N):
    costlist = list(map(int, input().split()))
    mylist += [costlist]
#print(mylist)

mymin =  float('INF')
for i in range(2 ** N):             #①
    myflag = [0 for i in range(N)]  #結果を出力するためのlistの初期化
    for j in range(N):
        if ((i >> j) & 1):          #②
            myflag[n - 1 - j] = 1

    mycost = 0
    myab = [0 for m in range(M)]
    #print(myflag, myab)
    for n in range(N):
        if myflag[n] == 1:
            mycost += mylist[n][0]
            for m in range(M):
                myab[m] += mylist[n][m+1]
    if min(myab) >= X:
        if mycost < mymin:
            mymin = mycost
            
if mymin == float('INf'):
    print(-1)
else:
    print(mymin)

Submission status: Accepted

Solution code:
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())


    

n,m,x=mi()

a=[[0 for i in range(m)]for j in range(n)]
p=[0]*n
for i in range(n):
    a1=li()
    p[i]=a1[0]
    a[i]=a1[1:]

ans=1000000007
for i in range(1,pow(2,n)):
    s=bin(i)[2:]
    s='0'*(n-len(s))+s
    s1=0
    x1=[0]*m
    for j in range(n):
        if s[j]=='1':
            for k in range(m):
                x1[k]+=a[j][k]
            s1+=p[j] 
    f1=1
    for j in range(m):
        if(x1[j]<x):
            f1=0
        
    if(f1):
        ans=min(ans,s1)
if(ans==1000000007):
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
def input_int_list():
    return [int(thing) for thing in input().split(" ")]

def int_input():
    return int(input())


def print_ans(string):
    print(string)
    exit()

def yes():
    print("Yes")
    exit()

def no():
    print("No")
    exit()

import numpy as np

N,M,X=input_int_list()
np_list=[np.array(input_int_list(),dtype=int) for i in range(N)]
kakaku_list=[]
for i in range(2**N):
    the=np.zeros((1,M),dtype=int)
    kakaku=0
    for j in range(N):
        if format(i,"b").zfill(N)[j]=="1":
            the=the+np_list[j][1:]
            kakaku=kakaku+np_list[j][0]
    if (the>=X).all():
        kakaku_list.append(kakaku)
if len(kakaku_list)!=0:
    print_ans(min(kakaku_list))
else:
    print_ans(-1)

Submission status: Accepted

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

ans = 10**15
flag = False
for i in range(2**N):
    r = np.array([0]*(M+1))

    for j in range(N):
        if (i>>j)&1:
            for k in range(M+1):
                r[k] += A[j][k]
    #print(r)
    if np.all(r[1:]>=X):
        if ans > r[0]:
            ans = r[0]
        flag = True
    else:
        flag = False
        
if flag:
    print(ans)
else:
    print("-1")

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
N,M,X = map(int,input().split())
setto = list(range(N))
ans = 10**18
sankosyo = [list(map(int,input().split())) for i in range(N)]
subsets = []
for i in range(N+1):
    for c in combinations(setto,i):
        subsets.append(c)
for subset in subsets:
    cost = 0
    rikaido = np.array([0]*M)
    if subset == set():
        continue
    for i in subset:
        cost += sankosyo[i][0]
        for idx,A in enumerate(sankosyo[i][1:]):
            rikaido[idx] += A
    if np.count_nonzero(rikaido < X) == 0:
        ans = min(ans,cost)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = [int(x) for x in input().split()]
C = [None] * N
A = [None] * N
for i in range(N):
    K = [int(x) for x in input().split()]
    C[i] = K[0]
    A[i] = K[1:]
INF = float('inf')

ans = INF
for n in range(1, 2 ** N):
    select = bin(n)[2:].zfill(N)
    cost = 0
    S = [0] * M # 理解度
    for i in range(N): # 各本について
        if int(select[i]) == 0: continue
        cost += C[i]
        for j in range(M): # 各スキルについて
            S[j] += A[i][j]

    if cost >= ans: continue
    for j in range(M):
        if S[j] < X: break
    else:
        ans = cost

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for _ in range(N):
    ci,*ai = map(int,input().split())
    C.append(ci)
    A.append(ai)
# もし全部買っても理解度が足りなければ不可能
sum_x = [0 for i in range(M)]
for i in range(N):
    ai = A[i]
    for j,aij in enumerate(ai):
        sum_x[j] += aij
min_x = min(sum_x)
if min_x<X:
    print('-1')
    exit()

# 普通にビット探索
import math
max_bit = 2**(N)
min_expense = math.inf
for i in range(2**(N)):
    binary = bin(max_bit+i)[1+2:]
    sum_x = [0 for _ in range(M)]
    expense = 0
    for j,b in enumerate(binary):
        if b=='1':
            expense += C[j]
            for k,ajk in enumerate(A[j]):
                sum_x[k] += ajk
    min_x = min(sum_x)
    if min_x<X:
        continue
    min_expense = min(expense,min_expense)

print(min_expense)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m, x = input_to_int_map()
    ca = [input_to_int_tuple() for i in range(n)]

    import itertools
    ret = 10 ** 10
    for temp in itertools.product([0, 1], repeat=n):
        money = 0
        understands = [0] * m
        for i, val in enumerate(temp):
            if val == 1:
                t_ca = ca[i]
                money += t_ca[0]
                a = t_ca[1:]
                for j, under in enumerate(a):
                    understands[j] += under
        if len(list(filter(lambda t : t >= x, understands))) == m:
            ret = min(ret, money)

    if ret == 10 ** 10:
        ret = -1

    return ret


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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
import numpy as np
import itertools

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

arr = np.array(l)

minimum = 10 ** 5 * 13
for boo in itertools.product([True, False], repeat=n):
    if arr[np.array(list(boo))].sum(axis=0)[1:m+1].min() >= x:
        temp = arr[np.array(list(boo))].sum(axis=0)[0]
        if temp < minimum:
            minimum = temp

if arr.sum(axis=0)[1:m+1].min() < x:
    print(-1)
else:
    print(minimum)

Submission status: Accepted

Solution code:
import numpy as np

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

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

ans = 1000000000
found = False

for i in range(2 ** N):
    tmp = [0] * (M + 1)
    books = np.array(tmp)
    for j in range(N): 
        if ((i >> j) & 1):
            books = books + np.array(C[j])

    skill_good = True
    for k in range(1,M+1):
        if books[k] < X:
            skill_good = False

    if books[0] < ans and skill_good:
        ans = books[0]
        found = True

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

Submission status: Accepted

Solution code:
import itertools
def main():
    N,M,X = map(int, input().split())
    C = [0 for i in range(N)]
    A = [[0]*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:(M+1)]

    texts_no = [i for i in range(N)]
    price_min = 0
    for i in range(1,N+1):
        # 教科書i冊(0~i-1)を選ぶ組み合わせ
        cmb = list(itertools.combinations(texts_no,i))
        for cmbset in cmb:
            # 理解度all0に初期化
            understand = [0 for _ in range(M)]
            price_tmp = 0
            for text in cmbset:
                understand = [understand[j]+A[text][j] for j in range(M)]
                price_tmp += C[text]
            # 条件を満たすなら最小値を更新
            joken = [True if n>=X else False for n in understand]
            if False not in joken:
                if price_min==0: price_min = price_tmp
                else: price_min = min(price_min, price_tmp)

    if price_min!=0: print(price_min)
    else: print(-1)


main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import math
# from pprint import pprint
import numpy as np


N,M,X = map(int, sys.stdin.readline().strip().split())
C = []
for _ in range(0, N):
    C.append(list(map(int, sys.stdin.readline().strip().split())))

# N = 3
# M = 3
# X = 10
#
# C = [
#     [60,2,2,4],
#     [70,8,7,9],
#     [50,2,3,9],
# ]

C.sort(key=lambda x:x[0])

ans = None
for i in range(1, N+1):
    for j in itertools.combinations(C, i):
        l = [k[1:] for k in j]
        # pprint(l)
        if len(l) > 1:
            ll = np.sum(l, axis=0)
            # print(ll)
            flag = all((m >= X) for m in ll)
        else:
            flag = all((m >= X) for m in l[0])
        if flag:
            n = np.sum(j, axis=0)[0]
            if ans == None or  ans > n:
                ans = n

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

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
z = [list(map(int, input().split())) for _ in range(n)]
nux = 10**13
for i in range(2**n):
    alu = [-x]*m
    buy = []
    for j in range(n):
        if (i >> j) & 1:
            buy.append(j)
    num = 0
    if i == 30:
        s = 1
    for k in buy:
        num += z[k][0]
        for ss in range(m):
            alu[ss] += z[k][ss+1]
    if len([i for i in alu if i < 0]) == 0:
        nux = min(num, nux)
if nux == 10**13:
    print(-1)
else:
    print(nux)