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 itertools
import math
import fractions
import functools

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

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


nums = []
for i in range(n):
    nums.append(i)

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i):
        rikaido = [0] * (m+1)
        for j in range(len(v)):
            for k in range(m+1):
                rikaido[k] += a_do[v[j]][k]

        temp.append(rikaido)

minimum = 10**20
for i in range(len(temp)):
    ok = True
    for j in range(1, m+1):
        if temp[i][j] < x:
            ok = False
    if(ok):
        minimum = min(minimum, temp[i][0])

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Submission status: Accepted

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

n,m,x = (int(x) for x in input().split())
seq = []
for _ in range(n):
    seq.append([int(i) for i in input().split()])
ans = float('inf')
for i in xrange(2**n):
    cost = 0
    knowledge = [0 for _ in xrange(m)]
    for j, c in enumerate(bin(i)[2:], n-len(bin(i)[2:])):
        if c =='1':
            cost += seq[j][0]
            for k in xrange(m):
                knowledge[k] += seq[j][1+k]
    if all([val >= x for val in knowledge]):
        ans = min(cost, ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=list(map(int,input().split()))
ans=10**18
A=[list(map(int,input().split())) for i in range(n)]
for i, _ in enumerate(A,1):
  for j in itertools.combinations(A,r=i):
    B=list(zip(*j))
    
    C=[0]*(m+1)
    for m in range(m+1):
      C[m]=sum(B[m])
    if len([i for i in C[1:] if i>=x ])==m:
      ans=min(ans,C[0])
print(ans) if ans!=10**18 else print(-1)

Submission status: Accepted

Solution code:
import numpy as np  # NumPyモジュールをインポートする
import itertools

val = input()
val = val.split(" ")
val = [int(i) for i in val]  # 全部intに変換

I = np.zeros((val[0], val[1]+1))

for i in range(val[0]):
    val2 = input()
    val2 = val2.split(" ")
    val2 = [int(i) for i in val2]  # 全部intに変換
    I[i] = val2

seq = [i for i in range(val[0])]  # 組み合わせを考える
# print(seq)

ans = []

for i in range(val[0]):
    Comb = list(itertools.combinations(seq, i+1))
    # print(Comb)
    for j in Comb:
        Com_list = list(j)
        # print(Com_list)
        I_sum = [[I[k][l+1] for k in Com_list] for l in range(val[1])]
        # print(I_sum)
        I_sum_over_x = [sum(m) for m in I_sum if sum(m) >= val[2]]
        # print('I_sum_over_x=', I_sum_over_x)
        if(len(I_sum_over_x) == val[1]):
            # print("xxx=", j)
            I_sum2 = [I[n][0] for n in list(j)]
            # print(I_sum2)
            # print(sum(I_sum2))
            ans.append(sum(I_sum2))

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

Submission status: Accepted

Solution code:
import numpy as np

max_n = 12
max_m = 12
def main():
    nmx = list(map(int, input().split()))
    c = [None]*nmx[0]
    a = [None]*nmx[0]
    for i in range(nmx[0]):
        ca = list(map(int, input().split()))
        c[i] = ca[0]
        a[i] = ca[1:]

    ms = -1
    # for i in range(nmx[0]):
    #     for j in range(i, nmx[0]):


    # dp = np.zeros([nmx[0], nmx[1]], dtype=int)
    # price = np.zeros([nmx[0]], dtype=int)
    # for i in range(nmx[0]):
    #     n = [i]
    #     for j in range(i):

    #         dp[i,j] = 
    poo = []
    for i in range(nmx[0]):
        poo.append([i])
        df(nmx[0], [i], poo)
    
    for i in poo:
        score = np.zeros([nmx[1]])
        p = 0
        for j in i:
            score += np.array(a[j])
            p += c[j]
        # print(score, nmx[2], score >= nmx[2])
        if all(score >= nmx[2]) and (ms > p or ms < 0):
            ms = p

    
    print(ms)

def df(n, m, store):
    
    for i in range(m[-1], n-1):
        tmp = list(m)
        tmp.append(i+1)
        store.append(tmp)
        df(n, tmp, store)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools

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

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


nums = []
for i in range(n):
    nums.append(i)
minimum = 10**20

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i): #参考書の選び方
        rikaido = [0] * (m+1)
        for j in range(len(v)):
            for k in range(m+1):
                rikaido[k] += a_do[v[j]][k]

        ok = True
        for j in range(1, m+1):
            if rikaido[j] < x:
                ok = False
        if(ok):
            minimum = min(minimum, rikaido[0])

#         temp.append(rikaido)

# minimum = 10**20
# for i in range(len(temp)):
#     for j in range(1, m+1):
#         if temp[i][j] < x:
#             break
#         minimum = min(minimum, temp[i][0])

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Submission status: Accepted

Solution code:
import numpy as np
INF = 10**9

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

choose = [True, False]

min_price = INF

for s in range(1 << N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s >> i & 1:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

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

Submission status: Accepted

Solution code:
n,m,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
i = 0
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)
i = 0
for i in range(2 ** n):
    for j in range(n):
        if ((i >> j) & 1):
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]
i = 0
j = 0
ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, x = map(int, readline().split())
ca = [list(map(int, readline().split())) for _ in range(n)]
ans = float('inf')
for bit in product([0, 1], repeat=n):
    cnt = 0
    memo = [0] * m
    for i in range(n):
        if bit[i] == 1:
            cnt += ca[i][0]
            for j in range(m):
                memo[j] += ca[i][j + 1]
    for j in range(m):
        if memo[j] < x:
            break
    else:
        ans = min(ans, cnt)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m,x = MI()
a = []
c = []
for i in range(n):
  dd = LI()
  c.append(dd[0])
  dd = dd[1:]
  a.append(dd)


INF = 1e14
ans = INF
for iters in range(1,n+1):
  xx = list(itertools.combinations(range(n), iters))
  for u in xx:
    bad = False
    score = [0] * m
    money = 0
    for i in u:
      money += c[i]
      for j in range(m):
        score[j] += a[i][j]

    for j in range(m):
      if score[j] < x:
        bad = True
        break
    # print(u, money, score)
    if not bad:
      ans = min(money, ans)

  # if ans < INF:
  #   break
    
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X = map(int, input().split())
CA = np.zeros((N,M+1))
for i in range(N):
    CA[i] = np.array(list(map(int, input().split())))

nums = [0,1]
bools = np.array(list(itertools.product(nums, repeat=N)))
ans = 10000000
for i in range(len(bools)):
    sumCA = sum(bools[i].reshape((N,1))*CA)
    flag = 1
    for j in range(1,M+1):
        if sumCA[j] < X:
            flag = 0
    if flag and sumCA[0] < ans:
        ans = sumCA[0]
        
if ans == 10000000:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
import copy
 
def dfs(A, times):
    if times == N:
        if min(A[1:M+1]) >= X:
            ans[0] = min(A[0], ans[0])
        return
    dfs(copy.copy(A), times+1)
    for i in range(M+1):
        A[i] = A[i] + L[times][i]
    dfs(copy.copy(A), times+1)

N, M, X = map(int, input().split())
L = [0] * (N)
for i in range(N):
    L[i] = [int(x) for x in input().split()]

INF = float('inf')
ans = [INF]
tmp = [0] * (M+1)
dfs(tmp, 0)
if ans[0] == INF:
    ans[0] = -1
print(ans[0])

Submission status: Accepted

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

# 解けなかった
# N, M, X = map(int, input().split())
# values_list = []
# for i in range(N):
#     values = list(map(int, input().split()))
#     values_list.append(values)

# ans = 0
# for i in range(1, N+1):
#     for pair in itertools.combinations(values_list, i):
#         this_m_dict = {}
#         this_cost = 0
#         for item in pair:
#             for j in range(1, M+1):
#                 this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
#             this_cost += item[0]
#         for myvalue in this_m_dict.values():
#             if myvalue < X:
#                 break
#         ans = min(this_cost, ans)

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

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

INF = float('INF')
min_cost = INF

def dfs(i, cost, learn):
    if i == N:
        if min(learn) >= X: 
            return cost
        else:
            return INF

    else:
        new_learn = [(x+y) for (x, y) in zip(A[i], learn)]
        cost = min(dfs(i+1, cost, learn), dfs(i+1, cost + C[i], new_learn))
        return cost

min_cost = dfs(0, 0, [0] * M)

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

Submission status: Accepted

Solution code:
import numpy as np

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

choose = [True, False]

min_price = -1

for s in range(1 << N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s >> i & 1:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

if min_price == -1:
    print(-1)
else:
    print(min_price)

Submission status: Accepted

Solution code:
from itertools import product

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

bit = [0, 1]
ans = float('inf')
for l in product(bit, repeat=n):
    a = [0] * m
    cnt = 0
    for i, buy in enumerate(l):
        if buy == 1:
            cnt += ca[i][0]
            for j in range(1, m + 1):
                a[j - 1] += ca[i][j]
    if all(i >= x for i in a):
        ans = min(ans, cnt)

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

Submission status: Accepted

Solution code:
import sys
n,m,x= map(int, sys.stdin.readline().rstrip("\n").split())
lines = [ [int(s) for s in line.split()] for line in sys.stdin ]

books = {}
num = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                for e in range(2):
                    for f in range(2):
                        for g in range(2):
                            for h in range(2):
                                for i in range(2):
                                    for j in range(2):
                                        for k in range(2):
                                            for l in range(2):
                                                for o in range(2):
                                                    books[num] = [a,b,c,d,e,f,g,h,i,j,k,l]
                                                    num += 1
price = -1
skill = {}
for i in range(2**13-1):
    price_ = 0
    for j in range (m):
        skill[j] = 0
    for j in range(n):
        if books[i][j] == 1:
            price_  += lines[j][0]
            for k in range(m):
                skill[k] = skill[k] + lines[j][k+1]
        for k in range(m):
            if skill[k] < x:
                break
        else:
            if price == -1:
                price = price_
            else:
                price = min(price, price_)
print(price)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import copy
 
def dfs(A, times):
    if times == N:
        if min(A[1:M+1]) >= X:
            ans[0] = min(A[0], ans[0])
        return
    dfs(copy.copy(A), times+1)
    for i in range(M+1):
        A[i] = A[i] + L[times][i]
    dfs(copy.copy(A), times+1)

N, M, X = map(int, input().split())
L = [0] * (N)
for i in range(N):
    L[i] = [int(x) for x in input().split()]

INF = float('inf')
ans = [INF]
tmp = [0] * (M+1)
dfs(tmp, 0)
if ans[0] == INF:
    ans[0] = -1
print(ans[0])

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

N,M,X=map(int, input().split())
list_=[list(map(int, input().split())) for _ in range(N)]
cost=100000001
list_C=[]

for i in range(N):
	list_C=np.array(list(combinations(list_,N-i)))
	count=0
	#print(list_C)
	for h in range(len(list_C)):
		if all(np.sum(list_C[h], axis=0)[1:]>=X):
			if np.sum(list_C[h], axis=0)[0]<cost:
				cost=np.sum(list_C[h], axis=0)[0]
			#print(np.sum(list_C[h], axis=0),cost)
			count+=1
	if count==0:
		break

print(cost if cost<100000001 else "-1")

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = map(int,input().split())
CA = [np.array(list(map(int,input().split()))) for i in range(N)]
ans = -1
for i in range(1,2**N):
    und = np.zeros(M+1,dtype=int)
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            und += CA[j]
    for k in range(M):
        if und[k+1] < X:
            flag = False
            break
    if flag:
        tmp = und[0]
        if ans == -1:
            ans = tmp
        else:
            ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
def dp(start,algo,cost):
	if start>n:
		return
	global ans
	if all([True if i>=x else False for i in algo ]):
		ans = min(ans, cost)

	for i in range(start,n):
		temp = list(algo)
		for j in range(1,m+1):
			temp[j-1] += arr[i][j]
		dp(i+1, temp, cost+arr[i][0])

for tt in range(1):
	n,m,x = map(int,input().split())
	arr = []
	cost = [0]*m
	ans = float('inf')
	for i in range(n):
		l = list(map(int,input().split()))
		arr.append(l)
	dp(0,cost,0)
	if ans != float('inf'):
		print(ans)
	else:
		print(-1)

Submission status: Accepted

Solution code:
import numpy as np

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

min_cost = 10 ** 9
for bit in range(1, 1 << n):
  purchase = np.zeros(m + 1, dtype=int)
  for i in range(n):
    if bit & 1:
      purchase += books[i]
    bit >>= 1
  if np.all(purchase[1:] >= x):
    min_cost = min(min_cost, purchase[0])
if min_cost == 10 ** 9:
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
import itertools

num_book, num_algo, target_score = map(int, input().split())

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

all_comb_book_info_list = []
for n in range(1, len(book_info_list) + 1):
    for conb in itertools.combinations(book_info_list, n):
        all_comb_book_info_list.append(list(conb))

price = -1
for comb_book_info_list in all_comb_book_info_list:
    book_info_total = [0] * (num_algo + 1) # cost + アルゴリズム数
    for book_info in comb_book_info_list:
        book_info_total = [x + y for (x, y) in zip(book_info_total, book_info)]
    is_score_satisfied = True
    for total_score in book_info_total[1:]:
        if total_score < target_score:
            is_score_satisfied = False
        if not is_score_satisfied:
            break
    if not is_score_satisfied:
        continue
    if price == -1 or book_info_total[0] < price:
        price = book_info_total[0]

print(price)

Submission status: Accepted

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

master = [0 for i in range(M)]
bought = [False for i in range(N)]
cost = 0

def f(master, book):
    for i in range(M):
        master[i] += book[i]
    return master

for i in range(N):
    c, *a = list(map(int, input().split()))
    C.append(c)
    A.append(a)

m = 10**100
for i in range(2**N):
    cost = 0
    master = [0 for i in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            master = f(master, A[j])
    if min(master) >= X:
        m = min(m, cost)
    if i == 2**N-1 and min(master) < X:
        m = -1
        
print(m)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools

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

c = []
a_do = []
for i in range(n):
    a = list(map(int, input().split()))
    c.append(a[0])
    a_do.append(a[1:])

# minimum = 10**20
# for pat in range(0, (1<<n)): #参考書の選び方の全パターン
#     cost = 0
#     rikaido = [0] * m
#     for i in range(n):
#         if((pat >> i) & 1): #i番目の参考書を読む
#             cost += c[i]
#             for k in range(m):
#                 rikaido[k] += a_do[i][k]
#     ok = True
#     for k in range(m):
#         if(rikaido[k] < x):
#             ok = False
#     if(ok):
#         minimum = min(minimum, cost)

# if(minimum == 10**20):
#     print(-1)
# else:
#     print(minimum)

minimum = 10**20

nums = []
for i in range(n):
    nums.append(i)

temp = []
for i in range(1, n+1):
    for v in itertools.combinations(nums, i):
        cost = 0
        rikaido = [0] * (m)
        for j in range(len(v)):
            cost += c[v[j]]
            for k in range(m):
                rikaido[k] += a_do[v[j]][k]

        ok = True
        for k in range(m):
            if rikaido[k] < x:
                ok = False

        if(ok):
            minimum = min(minimum, cost)


#         temp.append(rikaido)

# minimum = 10**20
# for i in range(len(temp)):
#     for j in range(1, m+1):
#         if temp[i][j] < x:
#             break
#         minimum = min(minimum, temp[i][0])

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int, input().split())
book = []
for i in range(n):
  b = list(map(int, input().split()))
  book.append(b)
book = sorted(book, key=lambda x:x[0])
junretu = itertools.permutations(range(n))
max_ = 2**n
min_nedan = 10**9
for j in range(max_):
  bit = format(j, "0"+str(n)+"b")
  count_list = [0]*m
  nedan = 0
  for b in range(n):
    if bit[b] == "1":
      naiyou = book[b]
      nedan += naiyou[0]
      for i in range(1, m+1):
        count_list[i-1] += naiyou[i]
  if min(count_list)>=x:
    if nedan < min_nedan:
      min_nedan = nedan
if min_nedan == 10**9:
  print(-1)
else:
  print(min_nedan)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 1e18
for i in range(1 << n):
    b = [0] * m
    c = 0
    for j in range(n):
        if i & (1 << j):
            c += a[j][0]
            for k in range(m): b[k] += a[j][k + 1]
    for j in range(m):
        if b[j] < x: c = 1e18
    ans = min(ans, c)
print(-1 if ans == 1e18 else ans)

Submission status: Accepted

Solution code:
def dfs(pos):
    global N,M,X,a,CA,ans
    if pos==N:
        res = 0
        comp = [0] * M
        for i in range(N):
            if a[i]:
                res += CA[i][0]
                for j in range(1,M+1):
                    comp[j-1] += CA[i][j]
        for i in range(M):
            if comp[i]<X:
                return
        ans = min(ans,res)
        return
    a[pos] = 0
    dfs(pos+1)
    a[pos] = 1
    dfs(pos+1)

N,M,X = map(int,input().split())
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))
ans = int(1e9)
a = [0] * N
dfs(0)
if ans==int(1e9):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

INF=float("INF")
min_cost=INF

def dfs(i,cost,learn):
    if i==N:
        if min(learn)>=X:
            return cost
        else:
            return INF
    else:
        new_learn=[x+y for (x,y) in zip(A[i],learn)]

        # ここの仕組みがよく分からない・・・
        cost=min(dfs(i+1,cost,learn),dfs(i+1,cost+C[i],new_learn))
        return cost

min_cost=dfs(0,0,[0]*M)

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

Submission status: Accepted

Solution code:
INF=float('inf')

def main():
    N,M,X=map(int,input().split())
    ans=INF
    CA=[[int(_) for _ in input().split()] for _ in range(N)]
    for bit in range(2**N):
        money=0
        tmp=[0]*M
        for i in range(N):
            if (bit >> i) & 1:
                money += CA[i][0]
                for j in range(1, M+1):
                    tmp[j-1] += CA[i][j]
        if min(tmp) >= X:
            ans=min(ans, money)
    print(-1 if ans == INF else ans)

main()

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools

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

c = []
a_do = []
for i in range(n):
    a = list(map(int, input().split()))
    c.append(a[0])
    a_do.append(a[1:])


minimum = 10**20
for pat in range(0, (1<<n)): #参考書の選び方の全パターン
    cost = 0
    rikaido = [0] * m
    for i in range(n):
        if((pat >> i) & 1): #i番目の参考書を読む
            cost += c[i]
            for k in range(m):
                rikaido[k] += a_do[i][k]
    ok = True
    for k in range(m):
        if(rikaido[k] < x):
            ok = False
    if(ok):
        minimum = min(minimum, cost)

if(minimum == 10**20):
    print(-1)
else:
    print(minimum)

Submission status: Accepted

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

INF=float("INF")
min_cost=INF

def dfs(i,cost,learn):
    if i==N:
        if min(learn)>=X:
            return cost
        else:
            return INF
    else:
        new_learn=[x+y for (x,y) in zip(A[i],learn)]
        cost=min(dfs(i+1,cost,learn),dfs(i+1,cost+C[i],new_learn))
        return cost

min_cost=dfs(0,0,[0]*M)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
    li=list(map(int,input().split()))
    C.append(li[0])
    A.append(li[1:])
ans=10**20
for i in range(2**N):
    li=[0]*M
    cost=0
    for j in range(N):
        if(i>>j&1):
            cost+=C[j]
            for k in range(M):
                li[k]+=A[j][k]
    ok=True
    for j in range(M):
        if(li[j]<X):
            ok=False
            break
    if ok:
        ans=min(ans,cost)
print(ans if ans!=10**20 else -1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, x = map(int, readline().split())
ca = list(map(int, read().split()))

flg = 0
c_min = 1000000000

for i in range(1, 2**n + 1):
    sum_a = [0] * (m+1)
    check = 0
    
    s = bin(i)[2:].zfill(n)
    for j in range(n):
        if s[j] == "1":
            sum_a = [x + y for x, y in zip(sum_a, ca[(m+1)*j:(m+1)*(j+1)])]

    # 全てx以上かチェック
    for k in range(1, m+1):
        if sum_a[k] >= x:
            check += 1
        if check == m:
            c_temp = sum_a[0]
            flg = 1
            if c_temp < c_min:
                c_min = c_temp

if flg == 1:
    print(c_min)
else:
    print("-1")

Submission status: Accepted

Solution code:
def readinput():
    n,m,x=list(map(int,input().split()))
    dat=[]
    for i in range(n):
        s=list(map(int,input().split()))
        c=s[0]
        a=s[1:]
        dat.append((c,a))
    return n,m,x,dat

def makeTableA(dat,n,m):
    tbl=[[0]*m]*n
    #print(n,len(tbl),m,len(tbl[0]))
    for i in range(n):
        tup=dat[i]
        a=tup[1]
        #print(a)
        #for j in range(m):
        #    tbl[i][j]=a[j]
        tbl[i]=list(a) 
        #print(tbl) 
    return tbl  

def main(n,m,x,dat):
    tblA=makeTableA(dat,n,m)
    #print(tblA)
    tblB=[[0]*(m+2)]*2**n  #
    #print(n,m,len(tblB), len(tblB[0]))  
    for i in range(2**n):
        tblB[i]=[0]*(m+2)
        b=1
        for j in range(n):
            if(i&b==b):
                for k in range(m):
                    #print(j,k)
                    tblB[i][k]+=tblA[j][k]
                    #print(tblB)
                tblB[i][m]+=dat[j][0]
                #print(tblB)
            b=b*2
        tblB[i][m+1]=min(tblB[i][0:m])
        #print(tblB)
    #print(tblB)
    # テーブルをスキャンする
    Pmin=12*10**5+1
    for i in range(2**n):
        if(tblB[i][m+1]>=x):
            price=tblB[i][m]
            if(price < Pmin):
                Pmin=price
    if(Pmin==12*10**5+1):
        Pmin=-1
    return Pmin


if __name__=='__main__':
    n,m,x,dat=readinput()
    ans=main(n,m,x,dat)
    print(ans)

Submission status: Accepted

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

ans = 100000 * n + 1

for bit in range(1 << n):
    A = [0] * m
    csum = 0

    for i in range(n):
        if bit & (1 << i):
            for j in range(m):
                A[j] += a[i][j]
            csum += c[i]

    if min(A) >= x:
        ans = min(ans, csum)

print((ans if ans != 100000 * n + 1 else -1))

Submission status: Accepted

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

for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
ans=99999999
for i in range(2 ** n):
    bag = []
    for j in range(n):  
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enou=[0]*m
    mone=0
    for sub in bag:
        mone+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enou[kk-1]+=1
    if 0 not in enou:
        if ans>mone:
            ans=mone
if ans==99999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = 10**9
for i in range(2**n):
  cost = 0
  point = [0]*m
  for j in range(n):
    if (i>>j)&1:
      cost += books[j][0]
      for k in range(1, m+1):
        point[k-1] += books[j][k]
  flag = True
  for j in range(m):
    if point[j] < x:
      flag = False
  if flag and ans > cost:
    ans = cost

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import combinations

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    min_price = INF
    for r in range(1, N + 1):
        for comb in combinations(range(N), r):
            skills = [sum(A[i][j] for i in comb) for j in range(M)]
            if all(s >= X for s in skills):
                total_price = sum(c for i, c in enumerate(C) if i in comb)
                if min_price > total_price:
                    min_price = total_price

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

kingakumin = 10000000000

for i in range(2 ** n):
    now = []
    inow = i
    for j in range(n):
        now.append(i % 2)
        i = i // 2

    syuutoku = []
    for j in range(m):
        syuutoku.append(0)

    kingaku = 0
    for j in range(n):
        if now[j] == 1:
            kingaku = kingaku + cas[j][0]
            for k in range(m):
                syuutoku[k] = syuutoku[k] + cas[j][k + 1]

    flag = True
    for j in range(m):
        if syuutoku[j] < x:
            flag = False

    if flag and kingakumin > kingaku:
        kingakumin = kingaku

if kingakumin == 10000000000:
    kingakumin = -1

print(kingakumin)