Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

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

sum=[0]*(m+1)
minval=1200001
for i in range(0,2**n):
    sum=[0]*(m+1)
    for j in range(n-1,-1,-1):
        if i//(2**j)==1:
            for k in range(0,m+1):
                sum[k]+=a[j][k]
        i = i % (2**j)
    flag=0
    for l in range(1,m+1):
        if sum[l] < x:
            flag=1
            break;
    if flag==0:
        minval= min(minval,sum[0])

if minval==1200001:
    print("-1")
else:
    print(minval)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M, X = read_ints()
C, *A = read_col(N)


def ret_each_exp(p):
    exps = [0] * M
    money = 0
    # print(p)
    for i, pp in enu(p):
        if pp == 0:
            continue
        for m in range(M):
            exps[m] += A[m][i]
        money += C[i]
    return exps, money


def is_valid(exps):
    for e in exps:
        if e < X:
            return False
    return True


ans = INF
for p in product(range(2), repeat=N):
    exps, money = ret_each_exp(p)
    if is_valid(exps):
        ans = min(ans, money)
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
sL = [0]*m
bL = []
for i in range(n):
    book = list(map(int, input().split()))
    bL.append(book)


def fullS(currentL, index, allP):
    if index >= len(bL):
        if min(currentL) >= x:
            return allP
        else:
            return -1
    else:
        if min(currentL) >= x:
            return allP
        else:
            op1 = fullS(currentL, index+1, allP)
            newP = 0
            newL = []
            for i in range(len(bL[index])):
                if i == 0:
                    newP = allP+bL[index][i]
                else:
                    newL.append(currentL[i-1]+bL[index][i])
            op2 = fullS(newL, index+1, newP)
            if op1 == -1 and op2 == -1:
                return -1
            elif op1 == -1:
                return op2
            elif op2 == -1:
                return op1
            else:
                return min(op1, op2)
                


print(fullS(sL, 0, 0))

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
dic=[]
ans=10**18
ans_check=[0]*M
ans_t=0
for _ in range(N):
    dic.append(list(map(int,input().split())))
for i in range(0,2**N):
    tmp=i
    ans_t=0
    flag=0
    ans_check=[0]*M
    for j in range(N):
        index=tmp%2
        tmp=tmp//2
        if index==1:
            ans_t+=dic[j][0]
            for t in range(1,M+1):
                ans_check[t-1]+=dic[j][t]
    #print(ans_check)
    for d in ans_check:
        if d>=X:
            flag=1
        else:
            flag=0
            break
    if flag==1:
        ans=min(ans,ans_t)
    #print("ans",ans)
if ans==10**18:
    print(-1)
else:
    print(min(ans,ans_t))

Submission status: Accepted

Solution code:
import itertools

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_total_min = -1
for ci in range(1, N+1):  # 組み合わせの数
    for seq in itertools.combinations(range(N), ci): # 組み合わせのリスト
        C_total = 0
        A_total = [0] * M
        for ni in seq:
            C_total += C[ni]
            A_total = [A_total[ai] + A[ni][ai] for ai in range(M)]

        # 判定
        flag = True
        for ai in range(M):
            if A_total[ai] < X:
                flag = False
        if flag: # Trueなら
            if C_total_min == -1:
                C_total_min = C_total
            elif C_total_min > C_total:
                C_total_min = C_total
            else:
                pass

print(C_total_min)

Submission status: Accepted

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

s = float('inf')

for i in range(2 ** N):
    rikai = [0] * M
    total = 0
    is_rikai = True
    for j in range(N):
        if ((i >> j) & 1):
            total += (ca[j][0])
            for k in range(1, M + 1):
                rikai[k - 1] += ca[j][k]
    for l in rikai:
        if l < X:
            is_rikai = False
    if is_rikai:
        s = min(s, total)

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

Submission status: Accepted

Solution code:
n, m, x = [int(v) for v in input().split()]

c = [0] * n
a = [[] * m for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    c[i] = line[0]
    a[i] = line[1:]

ans = sum(c)
can = False
for i in range(1, 2 ** n):
    sumv = [0] * m
    sumc = 0
    for j in range(n):
        has_bought = i & 1
        if has_bought:
            sumc += c[j]
            for k in range(m):
                sumv[k] += a[j][k]
        i = i >> 1
    can = True
    for k in range(m):
        if sumv[k] < x:
            can = False
            break
    if can:
        ans = min(ans, sumc)

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

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, X = map(int, readline().split())

res = 0
A = [[0 for j in range(M)] for i in range(N)]
C = [0 for i in range(N)]

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

isPossible = True
for col in range(M):
    tmp = 0
    for row in range(N):
        tmp += A[row][col]
    if tmp < X:
        isPossible = False

if not isPossible:
    print(-1)
    exit()

res = sum(C)
for b in range(1 << N):
    isPossible = True
    tmp = 0
    acc = [0 for j in range(M)]
    for i in range(N):
        if b & 1 << i > 0:
            tmp += C[i]
            for j in range(M):
                acc[j] += A[i][j]

    for j in range(M):
        if acc[j] < X:
            isPossible = False
    if isPossible:
        res = min(res, tmp)
print(res)

Submission status: Accepted

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

import itertools

def main():

    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    x = s[2]

    iters = []
    ran = range(n)
    for i in range(n):
        comb = list(itertools.combinations(ran, i+1))
        iters.extend(comb)

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

    sum_list = []
    for comb in iters:
        flag = False
        budget = []
        score_list = [0 for x in range(m)]
        for index in comb:
            book = books[index]
            budget.append(book[0])
            book_score = book[1:]
            for i, bs in enumerate(book_score):
                score_list[i] += bs
            flags = [True if y >= x else False for y in score_list]
            flag = all(flags)
        if flag:
            sum_list.append(sum(budget))
    if len(sum_list) == 0:
        print(-1)
    else:
        print(min(sum_list))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

N, M, X = [ int(i) for i in input().strip().split(' ') ]

C = []
A = []
A_sum = [0] * M
for i in range(N):
    data = [ int(i) for i in input().strip().split(' ') ]
    C.append(data[0])
    A.append(data[1:])
    for j in range(M):
        A_sum[j] += data[j+1]

if min(A_sum) < X:
    print('-1')
else:
    min_C = float('inf')
    for n_select in range(1, N+1):
        for cmb in combinations(range(N), n_select):
            A_sum = [0] * M
            C_sum = 0
            for i in cmb:
                for j in range(M):
                    A_sum[j] += A[i][j]
                C_sum += C[i]
            if (C_sum < min_C) and (min(A_sum) >= X):
                min_C = C_sum
    print(min_C)

Submission status: Accepted

Solution code:
import itertools

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

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

a = itertools.product(range(2), repeat=n)

#print(list(a))
#print(ca)
cost = 100000000

for pr in list(itertools.product(range(2),repeat=n)):
#	print(pr)
	skill = [0 for i in range(m+1)]
	tcost = 0
	for i in range(n):
		if(pr[i] == 1):
			tcost+=ca[i][0]
			for j in range(1,m+1):
				skill[j]+=ca[i][j]
	
#	print(skill,tcost)
	
	flag = 1
	for j in range(1,m+1):
		if(skill[j] < x):
			flag=0
	if(flag==1):
		cost=min(cost,tcost)
		
if(cost == 100000000):
	print(-1)
else:
	print(cost)

Submission status: Accepted

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

num = [0,1]
p = itertools.product(num,repeat = n)

for i in p:
    tmp = [0 for i in range(m)]
    tmpans = 0
    for j in range(len(i)):
        if i[j] == 1:
            tmpans += c[j]
            for k in range(m):
                tmp[k] += a[j][k]
    if min(tmp) >= x:
        ans.append(tmpans)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

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

ans = (12 * (10**5)) + 1

for i in range(1, 2**n):
    money = 0
    skill = [0]*m
    for j in range(n):
        if (i >> j) & 1:
            money += C[j][0]
            for k in range(1, m+1):
                skill[k-1] += C[j][k]
    # スキルがx以上になったか判定する
    t = 0
    for sk in skill:
        if sk < x:
            t += 1
    if t == 0:
        ans = min(ans, money)
    # print(i, skill, money)

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

Submission status: Accepted

Solution code:
from operator import add
N, M, X = map(int, input().split())

price = []
effect = []
for _ in range(N):
    C, *A = map(int, input().split())
    price.append(C)
    effect.append(A)

ans = 10**10
flg = False
for bit in range(2**N):
    tmp_price = 0
    tmp = [0 for _ in range(M)]
    for i in range(N):
        if (1 << i) & bit:
            tmp = map(add, tmp, effect[i]) #理解度の管理
            tmp_price += price[i]

    if min(tmp) >= X:
        flg = True
        ans = min(ans, tmp_price)

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

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())

CA = [list(map(int, input().split())) for _ in range(N)]
CA = np.array(CA)
C = [CA[i][0] for i in range(N)]

ans = sum(C)

Flag = False

for i in range(2 ** N):
    A_count = np.zeros(M)
    C_count = 0
    bin_str = format(i, 'b')
    if len(bin_str) < N:
        bin_str = '0' * (N - len(bin_str)) + bin_str
    for j, s in enumerate(bin_str):
        if s == '1':
            A_count = A_count + CA[j][1:]
            C_count += CA[j][0]
    flag = True
    for k in range(M):
        if A_count[k] < X:
            flag = False
            break
    if flag and C_count <= ans:
        ans = C_count
        Flag = True

if Flag == False:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def solve(N, M, X, C, A):
    A = np.array(A)

    max_iq_list = sum(A)
    if min(max_iq_list) < X:
        print(-1)
        return

    cost_list = []
    for i in range(1, 2**N):
        book = []
        cost = 0
        for j in range(N):
            if ((i >> j) & 1):
                book.append(A[j])
                cost += C[j]
        if min(sum(np.array(book))) < X:
            pass
        else:
            cost_list.append(cost)

    print(min(cost_list))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    x = [int(i) for i in input().split()]
    c, a = x[0], x[1:]
    C.append(c)
    A.append(a)
over = 1000000000
ans = over
for Z in itertools.product(range(0, 2), repeat=N):
    ctotal = 0
    atotal = [0] * M
    for i in range(N):
        if Z[i] == 1:
            ctotal += C[i]
            for j in range(A[i].__len__()):
                atotal[j] += A[i][j]
    ok = True
    for a in atotal:
        if a < X:
            ok = False
    if ok:
        ans = min(ans, ctotal)

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

Submission status: Accepted

Solution code:
def sumList(index,array):
    if index ==n:
        sumArray.append(array)
    else:
        sumList(index+1,array)
        nextArray =[0]*(m+1)
        for i in range(m+1):
            nextArray[i] +=array[i]+ list[index][i]
        sumList(index+1,nextArray)



if __name__ == '__main__':
    n,m,x = map(int, input().split())

    list = []
    for i in range(n):
        a = [int(i) for i in input().split()]
        list.append(a)
    firstArray = [0] * (m + 1)
    sumArray = []
    sumList(0,firstArray)

    min = 100000000
    for i in sumArray:
        amount =0
        count =0
        for j in range(len(i)):
            if j == 0:
                amount =i[j]
            else:
                if i[j] >=x:
                    count+=1
        if count == m and min >= amount:
            min = amount

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

Submission status: Accepted

Solution code:
def main():
    from builtins import int, map, list, float, print, len, min
    from itertools import combinations
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N, M, X = input_number_list()
    C = []
    A = []
    for i in range(N):
        sc = input_number_list()
        C.append(sc[0])
        A.append(sc[1:])
    ls = []
    idxs = [i for i in range(N)]
    for i in range(0, N):
        for combi in combinations(idxs, i + 1):
            ls.append(combi)
    ans = float('inf')
    for i in range(len(ls)):
        money = 0
        xs = [0] * M
        is_ng = False
        for j in range(len(ls[i])):
            money += C[ls[i][j]]
            for k in range(len(A[ls[i][j]])):
                xs[k] += A[ls[i][j]][k]
        for n in range(len(xs)):
            if xs[n] < X:
                is_ng = True
                break
        if is_ng == False:
            ans = min(ans, money)
    if ans == float('inf'):
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
min_ = float('inf')
# print(ca)

for bit in range(1 << n):
#     print(bin(bit))
    cost = 0
    alg = [0]*m
    ok = [0]*m
    flag = 0
    for i in range(n):
#         print(bool(bit & 1<<i))
        if bool(bit & 1<<i) == 1:
            cost += ca[i][0]
#             print('hoge',ca[i][0])
            for j in range(1,m+1):
                alg[j - 1] += ca[i][j]
                if alg[j - 1] >= x:
                    ok[j - 1] = 1
        if ok.count(1) >= m:
            flag = 1
            break
#     print(cost)
    if flag == 1:
        min_ = min(min_,cost)
if min_ == float('inf'):
    print(-1)
else:
    print(min_)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, M, X = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in [0] * N]

    ans = float('inf')
    for mask in range(1, 1 << N):
        book = []
        for i in range(N):
            if mask & 1 << i:
                book.append(A[i])
        yen = 0
        m = [0] * M
        for a in book:
            yen += a[0]
            for i, v in enumerate(a[1:]):
                m[i] += v
        for i in m:
            if i < X:
                break
        else:
            ans = min(ans, yen)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)


main()

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m,x = MI()
c = [LI() for _ in range(n)]
ans = []

for i in range(2**n):
    c_sum = 0
    a = [0]*m
    for j in range(n):
        c_sum += int(format(i, '0'+ str(n) +'b')[j])*c[j][0]
        for k in range(m):
            a[k] += int(format(i, '0'+ str(n) +'b')[j])*c[j][k+1]
    if min(a) >= x:
        ans.append(c_sum)
if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import itertools

N, M, X = list(map(int, input().split()))
c_list = []
a_table = []
for _ in range(N):
    a_list = list(map(int, input().split()))
    a_table.append(a_list[1:])
    c_list.append(a_list[0])

p_list = list(itertools.product([True, False], repeat=N))
min_cost = float("inf")
for pattern in p_list:  # 4092 (10 ** 3)
    cost = 0
    rikai_list = [0] * M
    for n, is_buy in enumerate(pattern):  # N個  # 12
        # n番目の参考書
        if not is_buy:
            continue
        cost += c_list[n]
        for m, a in enumerate(a_table[n]):  # 12
            # m番目のアルゴリズム
            rikai_list[m] += a
    not_understand = [r for r in rikai_list if r < X]  # 12
    if not not_understand:
        min_cost = min(min_cost, cost)

ans = min_cost if min_cost != float("inf") else -1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
C = np.zeros(N, dtype=np.int)
A = np.zeros((N, M), dtype=np.int)

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


least_cost = np.inf


for pattern in range(2 ** N):
	knowledge = np.zeros(M, dtype=np.int)
	cost = 0
	
	for i in range(N):
		if (pattern >> i) & 1:
			cost += C[i]
			for j in range(M):
				knowledge[j] += A[i, j]
	
	if np.all(knowledge >= X) and cost < least_cost:
		least_cost = cost


if np.isinf(least_cost):
	print(-1)
else:
	print(least_cost)

Submission status: Accepted

Solution code:
import sys
import numpy

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, M, X = map(int, readline().split())
    cost = []; A = []
    for _ in range(N):
        c, *Atmp = map(int, readline().split())
        cost.append(c); A.append(Atmp)
    cost = numpy.array(cost)
    A = numpy.array(A)

    pay = []
    for i in range(2**N):
        jtmp = []
        costtmp = 0
        for j in range(N):
            if (i>>j)&1:
                jtmp.append(j)
        costtmp = cost[jtmp].sum()
        brain = A[jtmp,:].sum(axis=0)
        if all(brain >= X):
            pay.append(costtmp)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

c = []
score = []
for _ in range(n):
    inp = list(map(int, input().split()))
    c.append(inp[0])
    score.append(inp[1:])
c = np.array(c)
score = np.array(score)

ans = float('inf')
for i in range(2 ** n):
    scores = np.array([0] * m)
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            scores += score[j]
            cost += c[j]
    if all(scores >= x):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import  itertools
import numpy as np

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

#print(A)
l = [1, 0]
ll = list(itertools.product(l, repeat=N))
#print(ll)
ans = float("inf")
for i in ll:
    jdg = np.array([0] * (M+1))
    for k in range(N):
        if i[k] == 1:
             jdg = jdg + A[k]
    #print(jdg)
    if min(jdg[1:]) >= X:
        ans = min(ans,jdg[0])
    #print(min(jdg[1:]))
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())
C = [0 for i in range(N)]
A = [[0 for i in range(M+1)] for j in range(N)]
skill = [0 for i in range (M)]
ans = float('inf')
ans_check = 0
for i in range(N):
  A[i] = list(map(int,input().split()))
  C[i] = A[i][0]
A = np.array(A)
for i in range(2 ** N):
 # print(skill)
  skill = np.array([0 for i in range (M)])
  money = 0
  check = 0
  for j in range(N):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      for l in range(M):
        skill[l] += A[j][l+1]
      money += C[j]
  for k in range(M):
    if skill[k]<X:
      check = 1
      
  if check == 0:
    if money <= ans:
      ans = money
      ans_check = 1
  
if ans_check == 0:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import math

N, M, X = map(int, input().split())
costs = []
values = []
values_per_algs = [[] for _ in range(M)]
for _ in range(N):
  book = list(map(int, input().split()))
  costs.append(book[0])
  values.append(book[1:])
  for i in range(1, M+1):
    values_per_algs[i-1].append(book[i])

def rec(i, cost, val_per_algs):
  if i==N:
    if sum([1 if vals < X else 0 for vals in val_per_algs]) > 0:
      return math.inf
    else:
      return cost
  tmp_val_per_algs = val_per_algs.copy()
  for j in range(M):
    tmp_val_per_algs[j] += values[i][j]
  return min(rec(i+1, cost+costs[i], tmp_val_per_algs), rec(i+1, cost, val_per_algs.copy()))
  

def main():
  if sum([1 if sum(vals) < X else 0 for vals in values_per_algs]) > 0:
    print(-1)
    return
  print(rec(0, 0, [0 for i in range(M)]))
main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[]
for i in range(n):
  s=list(map(int,input().split()))
  l.append(s)
ans=12*(10**5)
#print(l)
import itertools
now=0
oko=0
com=[i for i in range(n)]
while now<=n:
  now+=1
  level=[0 for j in range(0,m+1)]
  for i in itertools.combinations(com, now):
    level=[0 for j in range(m+1)]
    money=0
    #print(i)
    for h in i:
      #print(h,"h")
      money+=l[h][0]
      for k in range(1,m+1):
        level[k]+=l[h][k]
    jud=0
    for ii in level:
      if ii>=x:
        jud+=1
    if jud==m:
      oko+=1
      #print("ok",i)
      ans=min(ans,money)
if oko==0:
  print("-1")
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
dp=[list(map(int,input().split())) for _ in range(n)]
c=0
gg=0
mas=[0]*m
a=(0,1)
ans=100000000
b=list(itertools.product(a,repeat=n))
for i in b:
    gg=0
    c=0
    mas=[0]*m
    for h in range(n):
        if i[h]==1:
            c+=dp[h][0]
            for t in range(m):
                mas[t]+=dp[h][t+1]
    for y in mas:
        if y<x:
            gg=1
    if gg==0:
        ans=min(ans,c)
        
if ans!=100000000:       
    print(ans)
else:
  print("-1")

Submission status: Accepted

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

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

ans = []

for i in range(2**n):
    _x = [0] * (m+1)
    _x[0] = x
    _ans = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                _x[k+1] += Y[j][k+1]
            _ans += Y[j][0]
    if min(_x) == x:
        ans.append(_ans)


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

Submission status: Accepted

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

C = []
A = []

for i in range(N):
    s = list(map(int, input().split()))
    
    C.append(s[0])
    A.append(s[1:])
    
import numpy as np

can = np.array(A).T

for i in range(M):
    if np.sum(can[i]) < X:
        print(-1)
        exit()

min = 100000000000
for i in range(2**N):
    switch = []
    for j in range(N):
        if ((i >> j) & 1):
            switch.append(j)
    #print("switch", switch)
    
    count = 0
    SUM = []
    for j in switch:
        SUM.append(A[j])
    
    can = np.array(SUM).T
    
    #print(can)

    flag = True
    for j in range(M):
        try:
            if np.sum(can[j]) < X:
                flag = False
                break
        except:
            flag = False
            break
        
    if flag:
        for j in switch:
            count += C[j]
        
        if count < min:
            min = count
        #print(count)
            
print(min)

Submission status: Accepted

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

for i in range(n):
  ary = list(map(int, input().split()))
  c[i] = ary[0]
  for j in range(m):
    a[i][j] = ary[j + 1]

ans = 10 ** 10
for i in range(2 ** n):
  cost = 0
  point = [0 for i in range(m)]
  for j in range(n):
    if i & (2 ** j) > 0:
      cost += c[j]
      for k in range(m):
        point[k] += a[j][k]
  flag = True
  for j in range(m):
    if point[j] < x:
      flag = False
      break
  if flag:
    ans = min(ans, cost)

print(ans if ans < 10 ** 10 else -1)

Submission status: Accepted

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

data=[]

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

kau=[False]*n

ans=[]

for i in range(2**n):
    check=1
    for j in range(n):
        if((i&check)!=0):
            kau[j]=True
        else:
            kau[j]=False
        check<<=1
    shujuku=[0]*m
    kakaku=0
    for j in range(n):
        if(kau[j]):
            kakaku+=data[j][0]
            for k in range(m):
                shujuku[k]+=data[j][1][k]
    ok=True
    for s in shujuku:
        if(s<x):
            ok=False
    if(ok):
        ans.append(kakaku)

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

Submission status: Accepted

Solution code:
def main():
    N,M,X = [int(x) for x in input().split()]
    Cl,All = [],[]
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        Cl.append(tmp[0])
        All.append((tmp[1:]))
    # print(Cl)
    # print(All)
    min_cost = sum(Cl) + 1
    for bit in range(1,1<<N):
        # print(bin(bit))
        cost = 0
        totalAl = [0]*M
        for i,al in enumerate(All):
            if (1<<i) & bit:
                # print(i)
                for j,a in enumerate(al):
                    totalAl[j] += a
                cost += Cl[i]
        check = True
        for a in totalAl:
            if a < X:
                check = False
        if check:
            min_cost = min(min_cost, cost)
    if min_cost > sum(Cl):
        print(-1)
    else:
        print(min_cost)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
conditions = [str(bin((2**N + i) & (2**(N+1) - 1)))[3:] for i in range(2**N)]
Q = [list(map(int, input().split())) for i in range(N)]
ans = -1
for c in conditions:
    res = [0]*(M+1)
    for i in range(N):
        if c[i] == '1':
            for j in range(M+1):
                res[j] += Q[i][j]

    failed = False
    for i in range(1, M+1):
        if res[i] >= X:
            continue
        else:
            failed = True
    if failed:
        continue
    else:
        if ans == -1:
            ans = res[0]
        else:
            ans = min(ans, res[0])

print(ans)

Submission status: Accepted

Solution code:

import numpy as np


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


N, M, X = inpl()

costs = []
aa = []
for _ in range(N):
    ca = inpl()
    costs.append(ca[0])
    aa.append(ca[1:])

aa = np.array(aa)
costs = np.array(costs)

ans = 10**10
for bit in range(1 << N):
    flags = [(bit >> i) & 1 == 1 for i in range(N)]
    rikai = aa[flags].sum(axis=0)
    if (rikai >= X).sum() == M:
        ans = min(ans, costs[flags].sum())


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