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())
book = [list(map(int, input().split())) for _ in range(n)]

A = []
C = []
for c, *a in book:
    C.append(c)
    A.append(a)

ans = float("inf")
for i in range(2 ** n):
    algo = [0] * m
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            cost += C[j]
            for idx, a in enumerate(A[j]):
                algo[idx] += a
    if all([True if a >= x else False for a in algo]):
        ans = min(ans, cost)

print(ans if ans != float("inf") else -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 =[0]*(m+1)

for i in range(m+1):
    for j in range(n):
        ans[i] = ans[i]+c[j][i]

if min(ans[1:]) < x :
    print(-1)
    exit()

tempans = [0]*(m+1)

for i in range(2 ** n):
    tempans = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m+1):
                tempans[k] = tempans[k]+c[j][k]
    if min(tempans[1:]) >= x and tempans[0] < ans[0]:
        ans[0] = tempans[0]

print(ans[0])

Submission status: Accepted

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

possible=False
ans=1000000000000000000
for i in range(0,2**N):
    bit=i
    rikai=[]
    cost=0
    for j in range(0,M):
        rikai.append(0)
    for j in range(0,N):
        if bit%2==1:
            cost+=A[j][0]
            for k in range(0,M):
                rikai[k]+=A[j][k+1]
        bit//=2
    sub=True
    for j in range(0,M):
        if(rikai[j]<X):
            sub=False
            break;
    if sub:
        possible=True
        ans=min(ans,cost)

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

Submission status: Accepted

Solution code:
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)

n,m,x = map(int, input().split())
a = []
c = []
for i in range(n):
    arr = list(map(int,input().split()))
    c.append(arr[0])
    a.append(arr[1:])
ans = 123456789
val = 1<<n
for mask in range(val):
    level = [0 for i in range(m)]
    cost = 0
    for i in range(n):
        if((mask>>i)&1):
            cost+=c[i]
            for j in range(m):
                level[j]+=a[i][j]
    ok = True
    for i in range(m):
        if(level[i] < x):
            ok = False
    if(ok):
        ans = min(cost, ans)
if(ans==123456789):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = 1200001
for pat in range(2**n):
    score = [0 for i in range(m)]
    cost = 0
    for i in range(n):
        if pat & (2**i):
            for j in range(m):
                score[j] += a[i][j]
            cost += c[i]
    if cost < ans:
        f = True
        for sc in score:
            if sc < x:
                f = False
                break
        if f:
            ans = cost
if ans == 1200001:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
List = []
for i in range(N):
  List.append(list(map(int, input().split())))
res1= 10000000000000
res2= -1
Flag2 = False

def CheckMaster(a):
  Flag = True
  for i in range(M):
    if a[i] < X:
      Flag = False
    else:
      continue
  return Flag
    
for bits in range(2**N):
  Master=[0]*M
  Money = 0
  for j in range(N):
    if((bits>>j) & 1): 
      Money += List[j][0]#金額の足し上げ
      for k in range(M):
        Master[k] += List[j][k+1]#成熟度の足し上げ
    if CheckMaster(Master):#成熟度の確認
      Flag2 = True
      res1 = min(res1,Money) #OK なら金額が最小か判断
    else:  #NGなら無視
      pass
if Flag2:
  print(res1)
else:
  print(res2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

import numpy as np

def main():
    n, m, x = map(int, input().split())
    c, a = [None]*n, [None]*n
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    
    def dfs(i, cost, A):
        if i == n-1:
            global ans
            if all([ai >= x for ai in A]) and cost < ans:
                ans = cost
            return
        i += 1
        dfs(i, cost, A[:])
        dfs(i, cost+c[i], A[:]+a[i])
    
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    ans = 10**7
    main()

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
ca_list = [list(map(int, input().split())) for i in range(n)]
money = []
for j in range(1, n + 1):
    ca_comb = itertools.combinations(ca_list, j)
    for ca_tuple in ca_comb:
        if all([sum([ca[i] for ca in ca_tuple]) >= x for i in range(1, m+1)]):
            money.append(sum([ca[0] for ca in ca_tuple]))
if money:
    print(min(money))
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
n, m, x = list(map(int,input().split()))
c = []
for i in range(n):
    c.append(list(map(int,input().split())))
mn = -1
for bn in itertools.product([0,1], repeat=n):
    money = 0
    skills = [0]*m
    for j in range(n):
        if bn[j] == 1:
            money += c[j][0]
            for k in range(m):
                skills[k] += c[j][k+1]
    if all([y >= x for y in skills]):
        if mn == -1:
            mn = money
        elif money < mn:
            mn = money
print(mn)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
d=[]
ans = []
for i in range(N):
    l=list(map(int,input().split()))
    d.append(l)
for i in range(2**N):
    u=[0]*M
    price=0
    for j in range(N):
           if ((i>>j) & 1):
                price+=d[j][0]
                for k in range(M):
                    u[k]+=d[j][k+1]
    if all(x>=X for x in u):
        ans.append(price)
print(min(ans) if len(ans) > 0 else -1)

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 10 ** 9 + 7
for l in list(itertools.product([0, 1], repeat=n)):
    cart = [0] * (m + 1)
    for i in [i for i, a in enumerate(l) if a == 1]:
        array = c[i]
        cart = list(map(lambda x,y: x+y, cart, array))
    if min(cart[1::]) >= x:
        ans = min(ans, cart[0])
        
print(ans if ans != 10 ** 9 + 7 else '-1')

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(100000)


def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    for i in range(n):
        cl[i], *al[i] = map(int, input().split())
    
    def dfs(i, cost, A):
        if i == n-1:
            global ans
            if all([a >= x for a in A]) and cost < ans:
                ans = cost
            return
        i += 1
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    
    dfs(-1, 0, np.array([0]*m))
    
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    ans = 10**7
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,X = inpl()
c = []
a = []
for _ in range(n):
    tmp = inpl()
    c.append(tmp[0])
    a.append(tmp[1:])

res = INF
for fl in itertools.product(range(2), repeat=n):
    ri = [0] * m
    cost = 0
    for i,x in enumerate(fl):
        if x:
            cost += c[i]
            for j,y in enumerate(a[i]):
                ri[j] += y
    if min(ri) >= X:
        res = min(res, cost)
print(res if res != INF 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):  #bit全探索
        if ((i >> j) & 1):
            bag.append(l[j])
    skill=[0]*m
    enough=[0]*m #各スキルにつき、xを超えているかどうかを判断
    money=0
    for sub in bag:
        money+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enough[kk-1]+=1
    if 0 not in enough: #全てのスキルがxを超えていたら価格を計算
        if ans>money:
            ans=money#最低価格を下回っていたら更新
if ans==99999999: #初期値からの変更がなければ-1を、そうでなければ最低価格を出力
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(100000)

def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    total = np.array([0]*m)
    global ans
    ans = 10**7
    for i in range(n):
        c, *a = map(int, input().split())
        a = np.array(a)
        cl[i] = c
        al[i] = a
        total += a
    def dfs(i, cost, A):
        i += 1
        if i == n:
            global ans
            if all([ai >= x for ai in A]) and ans > cost:
                ans = cost
            return
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(A):
    if len(A) == n:
        tmp = [0 for i in range(m+1)]
        for i, k in enumerate(A):
            if k:
                for j in range(m+1):
                    tmp[j] += a[i][j]
        chk = 0
        for i in range(1, m+1):
            if tmp[i] >= x:
                chk += 1
        if chk == m:
            ans[0] = min(tmp[0], ans[0])
        return

    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()


n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = [10**10]
dfs([])
if ans[0] != 10**10:
    print(ans[0])
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

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

min_cost = 10 ** 5 * 12 + 1
for i in range(1, n + 1):
    for j in list(itertools.combinations(range(n), i)):
        recog = [0] * m
        cost = 0
        for k in j:
            cost += c[k]
            for l in range(m):
                recog[l] += a[k][l]

        for l in range(m):
            if recog[l] < x:
                break
        else:
            if cost <= min_cost:
                min_cost = cost

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book_prices = []
book_effects = []
#get book data
for i in range(N):
  book_info = list(map(int, input().split()))
  book_price = book_info[0]
  book_effect = book_info[1:]
  book_prices.append(book_price)
  book_effects.append(book_effect)

#start finding min costs
min_cost = 2**63 - 1 #initialize with maximum number
for comb in range(2**(N)):
  #each combination ex) 000, 001, 011,,,
  cost = 0
  study_effect = []
  #initilalize study_effect with 0s
  for study_area in range(M):
    study_effect.append(0)
    
  for pos in range(N):
    #check which pos is 1(buy book)
    if (comb&(1<<pos) == (1<<pos)):
      #add cost and add book effect
      cost += book_prices[pos]
      book_effect = book_effects[pos]
      for study_area in range(M):
        study_effect[study_area] += book_effect[study_area]
  
  valid_books = True
  for effect in study_effect:
    if (effect < X):
      valid_books = False
      break
  if (valid_books):
    if (cost < min_cost):
      min_cost = cost

if (min_cost == 2**63 - 1):
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 7

for bit in range(2**n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if (bit >> i) & 1:
            cost += arr[i][0]
            for j in range(m):
                tmp[j] += arr[i][j+1]
    if all(tmp_ >= x for tmp_ in tmp):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 7

for bit in range(2**n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if (bit >> i) & 1:
            cost += arr[i][0]
            for j in range(m):
                tmp[j] += arr[i][j+1]
    for tmp_ in tmp:
        if tmp_ < x:
            break
    else:
        ans = min(ans, cost)

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

Submission status: Accepted

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

l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

price=[]
for i in range(2**n):
  check_list=[0]*(m+1)
  for j in range(n):
    if l[i][j]==1:
      for k in range(m+1):
        check_list[k]+=book[j][k]
  check=[]
  for p in range(1,m+1):
    if check_list[p]<x:
      check.append(False)
  if check==[]:
    price.append(check_list[0])

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

Submission status: Accepted

Solution code:
import glob
import os
import numpy as np


bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def rec(self, N, M, X, now_index, now_knowledge, now_price, books):

        if now_index > N:
            return 12 * 10**5 +1

        next_knowledge = now_knowledge + books[now_index][1:]
        if np.min(next_knowledge) >= X:
            result1 = now_price + books[now_index][0]
        else:
            result1 = self.rec(N, M, X, now_index+1, next_knowledge,  now_price + books[now_index][0], books)

        result2 = self.rec(N, M, X, now_index+1, now_knowledge,  now_price, books)

        if result1 < result2:
            return result1
        else:
            return result2

    def resolve(self):

        N, M, X = map(int, self.input_data().split())

        books = [None]*(N+1)
        for i in range(N):
            books[i+1] = np.array(list(map(int, self.input_data().split())))

        result = self.rec(N, M, X, 1, np.zeros(M), 0, books)
        if result == 12 * 10**5 +1:
            print('-1')
        else:
            print(str(result))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = list(map(int, input().split()))
a = np.zeros((N, M))
C = np.zeros(N)
for i in range(N):
    tmp = list(map(int, input().split()))
    C[i] += tmp[0]
    a[i] += tmp[1:]
    
answer_price = 10**10

for i in range(1 << N):
    tmp = np.zeros(M)
    cost = 0
    for j in range(N):
        if i % 2 == 1:
            tmp += a[j]
            cost += C[j]
        i = i >> 1

    if all(tmp >= X) and (cost < answer_price):
        answer_price = cost
        
if answer_price == 10**10:
    print("-1")
else:
    print(int(answer_price))

Submission status: Accepted

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

def skill_up(bit,m,x,c,a):

    acc_m = 10**9 + 1

    for can,acc_u in aaa(bit,m,x,c,a):
        if can < acc_m and all([s >= x for s in acc_u]):
            acc_m = can
    if acc_m > 10**9:
        return -1
    else:
        return acc_m

def aaa(bit,m,x,c,a):
    mx = 2**bit
    for i in range(1,mx):
        acc_u = [0] * m
        can = 0
        for b in range(bit):
            r = i & (1 << b)
            #print(x,type(x))
            if r != 0:
                v = int(math.log2(r))
                #print(i,(1 <<b ),v,c[v])
                for j in range(m):
                    acc_u[j] += a[v][j]
                can += c[v]
        #print(can,acc_u)
        #print(all([s >= 10 for s in acc_u]))
        yield can,acc_u

if __name__ == "__main__":
    n,m,x = map(int,input().split())
    c = []
    a = []
    for i in range(n):
        ca = list(map(int,input().split()))
        c.append(ca[0])
        a.append(ca[1:])

    #print(bit_check(n,m,x,c,a))
    print(skill_up(n,m,x,c,a))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
def bit_check(n,m,x,c,a):
    mx = 2**n
    bit = n
    acc_m = 10**9 + 1


    for i in range(1,mx):
        acc_u = [0] * m
        can = 0
        for b in range(bit):
            r = i & (1 << b)
            #print(x,type(x))
            if r != 0:
                v = int(math.log2(r))
                #print(i,(1 <<b ),v,c[v])
                for j in range(m):
                    acc_u[j] += a[v][j]
                can += c[v]
        #print(can,acc_u)
        #print(all([s >= 10 for s in acc_u]))
        if can < acc_m and all([s >= x for s in acc_u]):
            acc_m = can
    if acc_m > 10**9:
        return -1
    else:
        return acc_m
    
if __name__ == "__main__":
    n,m,x = map(int,input().split())
    c = []
    a = []
    for i in range(n):
        ca = list(map(int,input().split()))
        c.append(ca[0])
        a.append(ca[1:])

    print(bit_check(n,m,x,c,a))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
bl = []
for i in range(n):
  b = list(map(int, input().split()))
  bl.append(b)
ans = 10 ** 8

# bit全探索でそれぞれの本の読む / 読まない のパターンすべてを調べる
for i in range(1<<n):
  c = 0
  # 目標値を設定し、本を読んだら理解度を引く
  # 最終的にすべてが0以下なら全アルゴリズムを理解できた
  u = [x] * m
  
  for j in range(n):
    # 本のbitが立っていれば読んだものとして計算
    if i & 1<<j:
      b = bl[j]
      c += b[0]
      for k in range(1, m+1):
        u[k-1] -= b[k]
  # 最終的な理解度チェック
  if max(u) <= 0:
    ans = min(ans, c)

# ansに変更がない場合、目標に届かなかっったアルゴリズムがある
if ans == 10 ** 8:
  print('-1')
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
def main():
    INF=sys.maxsize
    N,M,X=tuple(map(int,sys.stdin.readline().split()))
    B=[]
    for _ in [0]*N:B.append([int(x) for x in sys.stdin.readline().split()])
    T=[0 for _ in range(M+1)]
    T[0]=INF
    for p in range(1,2**N):
        TT=[0 for _ in range(M+1)]
        for i in range(N):
            f=(p>>i)&1
            if f>0:TT=list(map(lambda x:x[0]+x[1],zip(TT,B[i])))
        F=list(map(lambda x:x>=X,TT[1:]))
        #print(f'TT[0], T[0], ... = {TT[0]}, {T[0]}, {F}')
        if TT[0]<T[0] and all(F):T=TT
    print(T[0]) if T[0]!=INF else print('-1')
if __name__=='__main__':main()

Submission status: Accepted

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(2 ** N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if (i >> j) & 1:
      cost += C[j]
      for k in range(M):
        skills[k] += A[j][k]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

Submission status: Accepted

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(1,N + 1):
  for comb in itertools.combinations(range(N),i):
    cost = 0
    skills = [0] * M
    for c in comb:
      cost += C[c]
      for j in range(M):
        skills[j] += A[c][j]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

costs = np.zeros(N, dtype=int)
up = np.zeros((N, M), dtype=int)
for i in range(N):
  l = list(map(int, input().split()))
  costs[i] = l[0]
  up[i, :] = l[1:]

# print(f"cost \n{costs}")
# print(f"up \n{up}")

b = [[False, True]] * N
min_cost = np.inf
# print(f"pattern : {len(list(product(*b)))}")
for p in product(*b):
  # print("===--" * 10)
  p = list(p)
  case_cost = np.sum(costs[p])
  case_up = np.sum(up[p, :], axis=0)
  if (case_up >= X).all() and min_cost > case_cost:
    min_cost = case_cost
if min_cost == np.inf:
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
As=[]
for _ in range(N):
  c,*a=map(int,input().split())
  C+=[c]
  As+=[a]
r=1e9
for i in range(2**N):
  cost=0
  perf=[0]*M
  for j in range(N):
    if (i>>j)&1:
      cost+=C[j]
      perf=[perf[k]+As[j][k] for k in range(M)]
  if all(p>=X for p in perf):
    r=min(r,cost)
if r==1e9:r=-1
print(r)

Submission status: Accepted

Solution code:
def solve():
    N, M, X = map(int, input().split())
    ans = 1000000000
    C = [0 for _ in range(N)]
    A = [[0 for _ in range(M)] for _ in range(N)]
    for j in range(N):
        C[j], *A[j] = map(int, input().split())

    for i in range(2 ** N):
        tmp = 0
        algorithm = [0 for _ in range(M)]
        for j in range(N):
            if (i >> j) & 1:
                for k in range(M):
                    algorithm[k] += A[j][k]
                tmp += C[j]
        if min(algorithm) >= X:
            ans = min(ans, tmp)

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
















if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
 
N, M, X = (int(v) for v in input().split())
c = [0]*N
a = [0]*N
 
for i in range(N):
    items = [int(v) for v in input().split()]
    c[i] = items[0]
    a[i] = items[1:]

# bit 探索
coin = list(itertools.product([0,1], repeat=N))
ans_cost = -1

for i in range(len(coin)):
    score = [0] * M
    for j in range(N):
        if coin[i][j] == 1:
            for k in range(M):
                score[k] += a[j][k]
    if min(score) >= X:
        cost = 0
        for l in range(N):
            cost += coin[i][l] * c[l]
        if (ans_cost == -1) | (cost < ans_cost):
            ans_cost = cost

print(ans_cost)

Submission status: Accepted

Solution code:
import sys
from itertools import product

import numpy as np

N, M, X = map(int, input().split(' '))
books = np.fromiter(sys.stdin.read().split(), dtype=int).reshape((N, M + 1))
indexes = np.arange(0, N, dtype=int)

min_cost = 10 ** 9
for bool_indexes in product((False, True), repeat=N):
    bool_indexes = list(bool_indexes)
    if np.min(np.sum(books[indexes[bool_indexes], 1:], axis=0)) >= X:
        min_cost = min(min_cost, books[indexes[bool_indexes], 0].sum())

if min_cost == 10 ** 9:
    min_cost = -1

print(min_cost)

Submission status: Accepted

Solution code:
import itertools

N, M, X = (int(v) for v in input().split())
c = [0]*N
a = [0]*N

for i in range(N):
    items = [int(v) for v in input().split()]
    c[i] = items[0]
    a[i] = items[1:]

coin = list(itertools.product([0,1], repeat=N))
ans_cost = -1

for i in range(len(coin)):
    score = [0] * M
    for j in range(N):
        if coin[i][j] == 1:
            for k in range(M):
                score[k] += a[j][k]
    if min(score) >= X:
        cost = 0
        for l in range(N):
            cost += coin[i][l] * c[l]
        if (ans_cost == -1) | (cost < ans_cost):
            ans_cost = cost

print(ans_cost)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
for i in range(n):
    ci = list(map(int,input().split()))
    c.append(ci)
t = [0 for i in range(m+1)]
def dfs(l,i):
    if i == n:
        if min(l[1:]) >= x:
            return l[0]
        else:
            return 10**9
    d = l[:]
    for j in range(m+1):
        d[j] += c[i][j]
    return min(dfs(l,i+1),dfs(d,i+1))
ans = dfs(t,0)
if ans == 10**9:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

ans = []
for i in range(2**n):
    v = i

    c_sum = 0
    a = [0 for _ in range(m)]
    for j in range(n):
        if v % 2 == 0:
            c_sum += cA[j][0]
            for k in range(m):
                a[k] += cA[j][k + 1]
        v //= 2

    if min(a) >= x:
        ans += [c_sum]

if len(ans) == 0:
    print(-1)
else:
    print(sorted(ans)[0])

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
 
C = []
A = []
for i in range(N):
    # この1行をtとする
    t = list(map(int, input().split()))
    C.append(t[0])
    # c以降はそれぞれAに代入
    A.append(t[1:])
 
result = -1
for i in range(1, 2 ** N):
    # 0をm個分複製 これはカウントだから別
    t = [0] * M
    c = 0
    # ここでのjは縦軸
    for j in range(N):
        # 1番目を右にシフトして 1 と論理積を取る　これがtrueならcにカウントしてt[k]に代入
        if (i >> j) & 1 == 0:
            continue
        # trueならc[j]円カウントする　最終的に180円になる
        c += C[j]
        for k in range(M):
            # Aj冊目のkをリストtにいれる 0 1 2 と順番に
            t[k] += A[j][k]
    # xが指定のXの理解度に達するまで上のtをチェック
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            # 上の結果のそうわの最小パターン
            result = min(result, c)
print(result)
# 出力結果
# [0, 0, 0]001
# [2, 2, 4]010
# [8, 7, 9]011
# [10, 9, 13]
# [2, 3, 9]
# [4, 5, 13]
# [10, 10, 18]
# [12, 12, 22]

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
table = [0]*M
ans = 10**9+7
cnt = 0
for bit in range(1<<N):
    table = [0]*M
    cnt = 0
    B = [(bit>>i)&1 for i in range(N)]
    for j in range(N):
        if B[j] == 1:
            for k in range(M):
                table[k] += A[j][k+1]
            cnt += A[j][0]
    if min(table) >= X:
        ans = min(ans,cnt)
if ans == 10**9+7:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ans=999999999999999999
a=[0]*n
for i in range(n):
  a[i]=list(map(int,input().split()))
for i in range(2**n):
  t=[0]*m
  temp=0
  for j in range(n):
    if (i>>j)&1:
      temp=temp+a[j][0]
      for k in range(m):
        t[k]=t[k]+a[j][k+1]
  if min(t)>=x:
    ans=min(ans,temp)
if ans==999999999999999999:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
cost = []
cont = []
INF = float('inf')
for _ in range(N):
    C, *A = map(int, input().split())
    cost.append(C)
    cont.append(A)
    
def calc(bit):
    price = 0
    skill = [0]*M
    for i in range(N):
        if (bit >> i) & 1:
            price += cost[i]
            for j, la in enumerate(cont[i]):
                skill[j] += la
    if min(skill) >= X:
        return price
    else:
        return INF
    
ans = INF
for bit in range(1 << N):
    price = calc(bit)
    ans = min(ans, price)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m, x = map(int, input().split())
a = np.dot([i for i in itertools.product([0, 1], repeat = n)],
           [list(map(int, input().split())) for _ in range(n)])
b = np.prod(a[:, 1:(m + 1)] >= x, axis = 1, dtype = bool)
print(min(a[:, 0][b]) if b.sum() else '-1')

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split(" "))
c=[]
a=[]
for i in range(n):
    tmp=[int(i) for i in input().split(" ")]
    c.append(tmp[0])
    a.append([])
    for j in range(m):
        a[i].append(tmp[j+1])
ans=int(1e9)
for mask in range(1<<n):
    w=[0]*m
    cost=0
    for i in range(n):
        if (mask>>i)&1:
            for j in range(m):
                w[j]+=a[i][j]
            cost+=c[i]
    ok=True
    for j in range(m):
        if w[j]<x:
            ok=False
    if ok:
        ans=min(ans,cost)
if ans==int(1e9):
    print("-1")
else:
    print(ans)