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=[[0 for j in range(m)] for i in range(n)]
c=[0]*n
for i in range(n):
    tmp=list(map(int,input().split()))
    c[i]=tmp[0]
    for j in range(m):
        a[i][j]=tmp[j+1]
#use bitmask to generate all subsets
ans=float('inf')
for mask in range(1<<n):
    tmp=[0]*m
    cost=0
    for i in range(n):
        if (mask>>i)&1:
            cost+=c[i]
            for j in range(m):
                tmp[j]+=a[i][j]
    flag=True
    for i in range(m):
        if tmp[i]<x:
            flag=False
            break
    if flag:
        ans=min(ans,cost)
print(ans) if ans!=float('inf') else print(-1)

Submission status: Accepted

Solution code:
import itertools

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

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

min = float('inf')
for i in range(n + 1):
  for com in list(itertools.combinations(a, i)):
    cost = 0
    skill = [0] * m
    for l in com:
      cost += c[a.index(l)]
      for mi in range(m):
        skill[mi] += l[mi]

    ans = True
    for sm in skill:
      ans = sm >= x and ans

    if ans and min > cost:
      min = cost

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

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_)
cc_ = []
for i in range(n):
    cc_.append(c_[i][0])
# print(cc_)

import numpy as np
import itertools
l_ = np.arange(n).tolist()

res_ = []
resList = []
flag = False
flag3 = True
if n == 1:
    for i in range(m):
        if c_[0][i+1] < x:
            # print(c_[0][i+1])
            flag3 = False
    print(cc_[0] if flag3 else -1)
else:
    for i in range(1,n+1):
        c = list(itertools.combinations(l_, i))
        for j in c:
            res_ = []
            flag2 = True
            for l in range(m):
                res = 0
                sum_money = 0
                for k in range(len(j)):
                    res += c_[j[k]][l+1]
                    sum_money += c_[j[k]][0]
                # print(res,sum_money)
                if res < x:
                    flag2 = False
            if flag2:
                resList.append(sum_money)
                flag = True
    # print(resList)
    print(min(resList) if flag else -1)

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) # 再帰限界変更（デフォルトは1000）

"""
# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = map(int,readline().rstrip().split()) # １行に複数の数値
A = list(map(int,readline().rstrip().split()))  # １行に複数の数値（リスト受け取り）
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

# 一行に文字列が一個 * n行
s_lis=[readline().rstrip().decode() for _ in range(n)] # .decodeはバイト列から文字列へ変換
# 一行に文字列が一個 * n行で文字列をアルファベット順に変換
s_lis=["".join(sorted(readline().rstrip().decode())) for _ in range(n)]
# 一行に文字列が複数個 * n行
s_lis=[readline().rstrip().split().decode() for _ in range(n)] # .decodeはバイト列から文字列へ変換

# 一行に数値が一個 * n行
s_lis=[int(readline().rstrip()) for _ in range(n)] 
# 一行に数値が複数個 * n行
s_lis=[int(readline().rstrip().split()) for _ in range(n)]

# dとAの行が交互に並んでいる場合
s = sys.stdin.readlines()
n, k=map(int, s[0].split())
d=[]
A=[]
for i in s[1:2*k:2]:
    d.append(int(i))
for i in s[2:2*k+1:2]:
    A.append(list(map(int, i.split())))
"""

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

costs = []
for i in range(2 ** n):
    flag = True
    cost = 0
    algos = [0] * m # 理解度のリスト作成
    op = [False] * n # 買う書籍をTrueとしてリスト作成、初期:[False, False, .. ,False]
    for j in range(n):
        if ((i >> j) & 1): # ビット演算
            op[n - j - 1] = True # ex) [False, True, .. ,False]
    # print(op)

    for j in range(n):
        if op[j]: # opの各インデックスにおいて True の場合
            # 引数にリスト指定したenumerate関数のループ：https://note.nkmk.me/python-enumerate-start/
            for ind, el in enumerate(ca[j][1:]): # 
                algos[ind] += el
            cost += ca[j][0]
            #print(algos)
    for j in algos:
        if j < x:
            flag = False
    if flag:
        costs.append(cost)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x = map(int,input().split())
a = [list(map(int, input().split())) for i in range(n)]
#print(a)
bit = (list(itertools.product([0,1], repeat=n)))
#print(bit)
d=[]
for i in range(len(bit)):
    kounyuu = []
    nedan=[]
    for j in range(n):
        if bit[i][j]==1:
            kounyuu.append(a[j])
            #print(kounyuu)
            c=[]
            for k in range(1,m+1):
                b = []
                for z in range(len(kounyuu)):
                    b.append(kounyuu[z][k])
                if(sum(b))>=x:
                    c.append(sum(b))
            if len(c)==m:
                for z in range(len(kounyuu)):
                    nedan.append(kounyuu[z][0])
                d.append(sum(nedan))
if d == []:
    print(-1)
else:
    print(min(d))

Submission status: Accepted

Solution code:
import itertools
n,m,k=map(int,input().split())
l=[[int(i) for i in input().split()] for l in range(n)]
min_price=10**8
min_list=[]
a=itertools.product([True,False],repeat=n)
for x in a:
    li=[0]*(m+1)
    for i,y in enumerate(x):
        if y:
            for z in range(m+1):
                li[z]+=l[i][z]
    if min_price>li[0]:
        f=True
        for o in li[1:]:
            if o<k:f=False
        if f:min_price=li[0]
print(min_price if min_price!=10**8 else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
min_can = set()


def cal_score(bought_books):
    global CA
    global M
    global N
    global X
    algo_Q = [0]*M
    cost = 0
    for i in range(N):
        if bought_books[i] == 1:
            for j in range(1, M+1):
                algo_Q[j-1] += CA[i][j]
            cost += CA[i][0]
    flag = True
    for i in range(M):
        if algo_Q[i] < X:
            flag = False
            break
    if flag:
        global min_can
        min_can.add(cost)
    return 0


def next_book(book_list):
    global N
    global M

    if len(book_list) == N:
       return cal_score(book_list)
    book_list.append(0)
    next_book(book_list)
    book_list.pop(-1)

    book_list.append(1)
    next_book(book_list)
    book_list.pop(-1)
    return 0


book_list = []
next_book(book_list)
if set() == min_can:
    print(-1)
else:
    print(min(min_can))

Submission status: Accepted

Solution code:
def solve():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 10**9
    for b in range(1<<N):
        cost = 0
        for i in range(N):
            if b>>i&1:
                cost += A[i][0]
        for j in range(M):
            cnt = 0
            for i in range(N):
                if b>>i&1:
                    cnt += A[i][j+1]
            if cnt<X:
                break
        else:
            ans = min(ans,cost)
    if ans==10**9:
        return -1
    return ans
print(solve())

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
data=[]
for i in range (n):
  a=list(map(int,input().split()))
  data.append(a)
mIN=10**7
for i in range(2**n):
  money=0
  bag=[]
  rikai=[0]*m
  cnt=[0]*m
  for j in range(n):
    if (i>>j)&1 :
      bag.append(data[j])
  for k in bag:
      money+=k[0]
      for s in range(m):
        rikai[s]+=k[s+1]
        if rikai[s]>=x:
          cnt[s]+=1
  if cnt.count(0)==0:
    mIN=min(mIN,money)
    
if mIN==10**7:
  print("-1")
else:
  print(mIN)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(n)]
ans = 193934993409409
for mask in range(2 ** n):
    C = [0] * m
    cst = 0
    for i in range(n):
        if (mask >> i) & 1:
            cst += X[i][0]
            for j in range(1, m + 1):
                C[j - 1] += X[i][j]
    if min(C) >= x:
        ans = min(ans, cst)
if ans < 91912922191:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

#%%
N, M, X = [int(i) for i in input().split()]
CA = [[] for i in range(N)]
for i in range(N):
    k = list(map(int, input().split()))
    CA[i] = k[:]
CA = np.array(CA)
#%%
cnt = (10 ** 5) * N + 1

for i in range(2 ** N):
    score = np.zeros(M + 1)
    for j in range(N):
        if (i >> j) & 1:
            score += CA[j]
    for k in range(1, M + 1):
        if score[k] < X:
            break
    else:
        if score[0] < cnt:
            cnt = score[0]
            
if cnt != (10 ** 5) * N + 1:
    print(int(cnt))
else:
    print(-1)

Submission status: Accepted

Solution code:
#abc_167_c
#itertools.productを使うバージョン

from itertools import product

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

INF = 1000000000000000000000000000
ans = INF


lists = list(product(list(range(2)), repeat = n))
for v in lists:
    '''
    for i in range(1<<n):  #n bits all searches
        # 1<<n == 2**n
    '''
    c = 0
    sums = [0]*m
    for j in range(n):
        if v[j]==1:        
            '''
            if i>>j & 1: #i>>j %2 == 1  is also fine.
            '''
            #apply this candidate. 
            c += costs[j][0]
            for k in range(m):
                sums[k] += costs[j][k+1]    
                
                
    if min(sums) >= x: #if all(s>=x for s in sums) でもよい
        ans = min(ans, c)                
    '''
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)
    でもよい。
    '''
    
        
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    import numpy as np
    N, M, X = map(int, input().split())
    C = [0] * N
    A = np.zeros((N, M), int)
    for i in range(N):
        B = list(map(int, input().split()))
        C[i] = B[0]
        for j in range(1, M+1):
            A[i, j-1] = B[j]

    #output
    #参考書はN冊ある。各々の教科書について、購入するかしないかで2**N通り。
    answer = pow(10, 9)
    import itertools

    L = itertools.product([True, False], repeat = N)

    for l in L:
        skill = np.zeros(M, int)
        temp_answer = 0
        for i in range(N):
            if l[i]:
                skill += A[i]
                temp_answer += C[i]
        if np.all(skill >= X):
            answer = min(temp_answer, answer)
    if answer != pow(10, 9):
        print(answer)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A=[0]*n
c=[0]*n

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

for i in range(n):
    c[i]= A[i][0]
    A[i] = A[i][1:]

import numpy as np
import sys

a = np.array(A)

ans = np.inf

for s in range(1<<n):
    cost = 0
    d = np.array([0]*m)
    for i in range(n):
        if s>>i&1:
            cost += c[i]
            d += a[i]
    if all(d >= x):
        ans = min(ans,cost)

print(ans if ans != np.inf else '-1')

Submission status: Accepted

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

'''
n,m,x = [int(i) for i in input().split()]
costs =[]

for i in range(n):
    a = [int(i) for i in input().split()]
    costs.append(a)
'''


INF = 1000000000000000000000000000
ans = INF

for i in range(1<<n):  #n bits all searches
    # 1<<n == 2**n
    c = 0
    sums = [0]*m
    for j in range(n):
        if i>>j & 1: #i>>j %2 == 1  is also fine.
            #apply this candidate. 
            c += costs[j][0]
            for k in range(m):
                sums[k] += costs[j][k+1]    
    '''
    cost = 0
    c = 0
    sums = [0] * m
    use_index=[]
    for j in range(n):
        if i%2==1:
            use_index.append(j)
        i >>= 1
    
    for v in use_index:
        c += costs[v][0]        
        for j in range(m):
            sums[j] += costs[v][j+1]
    '''
    
    #if min(sums) >= x:
    if all(s>=x for s in sums):
        ans = min(ans, c)
'''            
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)
'''
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

INF = 10**9
ans = INF
for i in range(2**N):
    skill = [0]*M
    yen = 0
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                skill[k] += A[j][k]
            yen += C[j]
    ok = True
    for j in skill:
        if j < X:
            ok = False

    if ok:
        ans = min(ans,yen)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools

n, m, x = [int(x) for x in stdin.readline().rstrip().split()]
c = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
c.sort()
mi = -1
r = 0

for j in range(1, m + 1):
    li = [x[j] for x in c]
    li.sort(reverse=True)
    for i in range(1, len(li) + 1):
        if sum(li[:i]) >= x:
            r = max(r, i)
            break

for h in range(r, n + 1):
    for i in itertools.combinations(c, h):
        cnt = [0] * m
        mon = 0
        for j in i:
            cnt = [cnt[k]+j[k+1] for k in range(len(cnt))]
            mon += j[0]
            if sum(1 for k in cnt if k >= x) == m:
                if mi > mon or mi == -1:

                    mi = mon
                break

print(mi)

Submission status: Accepted

Solution code:
def main():
    import itertools
    N, M, X = map(int, input().split())
    #c_list = []
    #a_list = []
    dict = {}
    c_dict = {}
    a_dict = {}
    count = 0
    count_list = []
    for i in range(1,N+1) :
        count = count + 1
        count_list.append(count)
        A_list = [A for A in input().split()]
        A_list = list(map(int, A_list))
        #c_list.append(A_list[0])
        #a_list.append(A_list[1:])
        dict[A_list[0]] = A_list[1:]
        c_dict[count] = A_list[0]
        a_dict[count] = A_list[1:]

    comb_lists = []
    for i in range(1, len(count_list)+1) :
        for comb_list in itertools.combinations(count_list, i) :
            comb_lists.append(list(comb_list))
    #print("comb_lists = %s" % comb_lists)
    result = -1
    for key_list in comb_lists :
        ans = 0
        t = [0] * M
        #print("key_list = %s" % key_list)
        for key in key_list :
            ans = ans + c_dict[key]
            #print("dict = %s" % c_dict[key])
            for j in range(M) :
                t[j] = t[j] + a_dict[key][j]
        #print("t = %s" % t)
        if all(x >= X for x in t) :
            if result == -1 :
                result = ans
            else :
                result = min(result, ans)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, k = [int(x) for x in input().split()]
li = [[int(x) for x in input().split()] for _ in range(n)]
prices = []
for bit in range(1, 2 ** n):
    index_list = []
    for i in range(n):
        if bit & 1 << i:
            index_list.append(i)
    c = 0
    for t in range(1, m + 1)        :
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1
        else:
            break
    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        prices.append(p)
if prices:
    print(min(prices))
else:
    print(-1)

Submission status: Accepted

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

MOD = 10**9+7
a = [0]*M
value = [0]
ans = MOD

for i in range(2**N):
    for j in range(N+1):
        if(i >> j) & 1:
            for k in range(M):
                a[k] += A[j][k+1]
            value.append(A[j][0])

    if min(a) >= X :
        ans = min(ans,sum(value))
    a = [0]*M
    value = []

print(-1 if ans == MOD else ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def saiki(count,price,lis):
    if count==N:
        judge=True
        for item in lis:
            if item<X:
                judge=False
        if judge:
            ans.append(price)
    else:
        temp=[lis[i]+note[count][i+1] for i in range(M)]
        saiki(count+1,price,lis)
        saiki(count+1,price+note[count][0],temp)

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

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

ans=[]
saiki(0,0,[0]*M)

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

Submission status: Accepted

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

'''
n,m,x = [int(i) for i in input().split()]
costs =[]

for i in range(n):
    a = [int(i) for i in input().split()]
    costs.append(a)
'''


INF = 1000000000000000000000000000
ans = INF

for i in range(1<<n):  #n bits all searches
    # 1<<n == 2**n
    c = 0
    sums = [0]*m
    for j in range(n):
        if i>>j & 1: #i>>j %2 == 1  is also fine.
            #apply this candidate. 
            c += costs[j][0]
            for k in range(m):
                sums[k] += costs[j][k+1]    
    '''
    cost = 0
    c = 0
    sums = [0] * m
    use_index=[]
    for j in range(n):
        if i%2==1:
            use_index.append(j)
        i >>= 1
    
    for v in use_index:
        c += costs[v][0]        
        for j in range(m):
            sums[j] += costs[v][j+1]
    '''
    
    if min(sums) >= x:
        ans = min(ans, c)
'''            
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)
'''
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
li = []
for t in range(n):
    li.append(list(map(int, input().split())))
price_list = []
for bit in range(1, 2**n):
    index_list = []
    for i in range(n):
        if bit & 1<<i:
            index_list.append(i)

    c = 0
    for t in range(1,m+1):
        s = 0
        for i in index_list:
            s += li[i][t]
        if s >= k:
            c += 1

    if c == m:
        p = 0
        for i in index_list:
            p += li[i][0]
        price_list.append(p)

if len(price_list):
    print(min(price_list))
else:
    print('-1')

Submission status: Accepted

Solution code:
Books,Cost,X=None,None,None
DP={}

def getUnderstanding(prev,curr):
    global Books
    L=[]
    for i in range(len(prev)):
        L.append(prev[i]+Books[curr][i])
    return L
def isUnderstandingReached(prev):
    global X
    for u in prev:
        if u<X:
            return False
    return True

def F(curr,prev):
    global Books,Cost,X,DP
    #if (curr,tuple(prev)) in DP:
    #    return DP[(curr,prev)]
    if isUnderstandingReached(prev):
        return 0
    if curr==len(Books):
        return float('inf')
    DP[(curr,tuple(prev))]=min(Cost[curr]+F(curr+1,getUnderstanding(prev,curr)),F(curr+1,prev))
    return DP[(curr,tuple(prev))]

N,M,X=map(int,input().strip().split())
Books=[]
Cost=[]
for i in range(N):
    L=list(map(int,input().strip().split()))
    Books.append(L[1:])
    Cost.append(L[0])
res=F(0,[0]*len(Books[0]))
if res==float('inf'):
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy
INF = 1001001001
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    k = list(map(int, input().split()))
    C.append(k[0])
    A.append(deepcopy(k[1:]))

ans = INF
for s in range(1 << N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if s >> i & 1:
            cost += C[i]
            for j in range(M):
                d[j] += A[i][j]
    ok = True
    for j in range(M):
        if d[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost)

if ans == INF:
    print('-1')
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
item=[list(map(int,input().split()))for i in range(n)]#金、アルゴリズムUp数
bag=[]#条件を満たす本の買い方
for i in range(2**n):#すべて調べる
    temp=[]#買う本
    job=[0]*m#理解度
    for s in range(n):#全桁を調べる
        if (i>>s)&1:#買うのであれば
            temp.append(s)#買う本を追加
            for y in range(m):
                job[y]+=item[s][y+1]#理解度を足す
    for s in range(len(job)):
        if job[s]<x:#もし、理解度がX未満であればbreak
            break
    else:#理解度がすべてX以上ならば
        money=0
        for s in temp:#合計金額を算出
            money+=item[s][0]
        bag.append(money)
#買う組み合わせが1以上なければ-1を出力
print(min(bag) if len(bag)>=1 else -1)

Submission status: Accepted

Solution code:
import sys

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, M, X = IL()
	c = [0] * N
	a = [[0] * M for _ in range(N)]
	for i in range(N):
		tmp = IL()
		c[i] = tmp[0]
		a[i][:] = tmp[1:]

	min_price = sys.maxsize
	for i in range(2**N):
		sum_price = 0
		rikaido = [0] * M
		for j in range(N):
			if (i>>j) & 1:
				sum_price += c[j]
				for k in range(M):
					rikaido[k] += a[j][k]
		if min(rikaido) >= X:
			min_price = min(min_price, sum_price)
	
	if min_price == sys.maxsize:
		print(-1)
	else:
		print(min_price)



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#bit探索でできるらしい
#URL:https://qiita.com/gogotealove/items/11f9e83218926211083a
n,m,x=map(int,input().split())
item=[list(map(int,input().split()))for i in range(n)]#金、アルゴリズムUp数
book=[i for i in range(n)]#本Nを表す
bag=[]#条件を満たす本の買い方
for i in range(2**n):#すべて調べる
    temp=[]#買う本
    job=[0]*m#理解度
    for s in range(n):#全桁を調べる
        if (i>>s)&1:#買うのであれば
            temp.append(s)#買う本を追加
            for y in range(m):
                job[y]+=item[s][y+1]#理解度を足す
    for s in range(len(job)):
        if job[s]<x:#もし、理解度がX未満であればbreak
            break
    else:#理解度がすべてX以上ならば
        money=0
        for s in temp:#合計金額を算出
            money+=item[s][0]
        bag.append(money)
#買う組み合わせが1以上なければ-1を出力
print(min(bag) if len(bag)>=1 else -1)

Submission status: Accepted

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

ans = float('inf')
for i in range(1<<N):
  tmp = [0]*(M+1)
  for j in range(N):
    if i&(1<<j)==0: continue
    for k,l in enumerate(A[j]):
      tmp[k] += l
  if all(e>=X for e in tmp[1:]):
    ans = min(ans, tmp[0])
if ans==float('inf'):
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

As = []

for i in range(N) :
  As.append(list(map(int, input().split())))
  
L_As = len(As[0])
cal = np.zeros(L_As)
ans = []
for j in range(1, N+1) :
  for k in itertools.combinations(As, j) :
    for l in k :
      cal = cal + np.array(l)
    if min(cal[1:L_As]) >= X :
      ans.append(cal[0])
    cal = np.zeros(len(As[0]))

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

Submission status: Accepted

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

input = sys.stdin.readline

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

books = []
for i in range(n):
	book = list(map(int, input().split()))
	books.append(book)
    
ans = float('inf')
for s in range(1 << n):
  cost = 0
  d = [0] * m
  for i in range(n):
    if (s >> i & 1):
      cost += books[i][0]
      for j in range(m):
        d[j] += books[i][j+1]
  ok = True
  for j in range(m):
    if(d[j] < x):
      ok = False
  if ok:
    ans = min(cost, ans)
if (ans == float('inf')):
  print("-1")
else :
  print(ans)

Submission status: Accepted

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

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


for i in range(2**n):
    b=bin(i)
    price=0
    score=[0 for k in range(m)]
    #print(b)
    # それぞれの組み合わせ
    for j in range(n):
        if ((i >> j) & 1):#二進数iの下から数えてj桁目が1か否か
            a=al[j]
            for k in range(m):
                score[k]=score[k]+a[k]
            price+=cl[j]
    # if x<
    if min(score)>=x:
        price_list.append(price)

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

Submission status: Accepted

Solution code:
INF = 1e10

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

ans = INF

for s in range(1<<N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if s>>i&1:
            cost += C[i]
            for j in range(M): d[j] += A[i][j]

    ok = True
    for j in range(M):
        if d[j] < X: ok = False
    if ok: ans = min(ans, cost)

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

Submission status: Accepted

Solution code:

# 再帰関数を利用して全ての組み合わせを求める
def loop(n_cnt, my_list):
    if n_cnt==n:     # 再帰の終了条件
        bool_list = [i>=x for i in my_list[1:]]
        if all(bool_list):
            ans.append(my_list[0])
    else:
        # 要素同士を足す
        add_list = [my_list[i] + CA[n_cnt][i] for i in range(m+1)]
        loop(n_cnt+1, my_list)
        loop(n_cnt+1, add_list)
        

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

ans = []

loop(0,[0]*(m+1))
print(min(ans) if len(ans)!=0 else '-1')

Submission status: Accepted

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

a = [[0 for i2 in range(12)] for i1 in range(12)]
c=[0]*N
for i in range(N):
    C=list(map(int,input().split()))
    c[i]=C[0]
    for j in range(M):
        a[i][j]=C[j+1]

INF=1200001
ans=INF

for s in range(1<<N):
    cost = 0
    d = [0]*M
    for i in range(N):
        if(s>>i&1):
            cost+=c[i]
            for j in range(M):
                d[j]+=a[i][j];
    ok=1
    for j in range(M):
        if d[j]<X:
            ok=0
    if(ok):
        ans=min(ans,cost)
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())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)

out = 10**18
for c in itertools.product([False, True], repeat=N):
    tmp = np.sum(items[np.where(c)], axis=0)
    if M == np.count_nonzero(tmp[1:] >= X):
      out = min(out, tmp[0])

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

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:]))
    # 参考書全て購入した金額+1円を最低金額の初期値に
    min_cost = sum(Cl) + 1
    # 0冊購入は考慮せず、1冊目からループ
    for bit in range(1, 1 << N):
        cost = 0
        # アルゴリズムM個の理解力を保持するリスト
        totalAl = [0]*M
        for i, al in enumerate(All):
            # 購入フラグが立っていればアルゴリズムの理解力と金額を更新
            if (1 << i) & bit:
                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)
    # 購入金額が初期値のままならば-1を出力
    if min_cost > sum(Cl):
        print(-1)
    else:
        print(min_cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(i, und, cost, cost_list):
    if i == n:
        for val in und:
            if val < x: break
        else:
            cost_list.append(cost)
        return

    dfs(i + 1, [x + y for x, y in zip(und, a[i])], cost + c[i], cost_list)
    dfs(i + 1, und, cost, cost_list)

    return min(cost_list) if cost_list else -1

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

rec = dfs(0, [0] * n, 0, [])
print(rec)

Submission status: Accepted

Solution code:
import numpy as np

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

data = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

data_all = []
c_min = INF

for i in range(2**N):
    data_tmp = [0]*M
    c = 0
    for j in range(N):
        if((i>>j) & 1):
            for k in range(M):
                data_tmp[k] += data[j][k+1]
            c += data[j][0]
    if(min(data_tmp) >= X):
        c_min = min(c, c_min)

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

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])
c = arr.T[0]
a = arr.T[1:].T

ans = np.inf
for i in range(2**n):
    ability = np.zeros(m, np.int64)
    cost = 0
    for j in range(n):
        if (i>>j)&1: ability += a[j] ; cost += c[j]
    if np.all(ability>=x): ans = min(ans,cost)

ans = -1 if ans==np.inf else ans
print(ans)