Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:
import sys
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())
data = np.array(read().split(), np.int64)
data = data.reshape(N,-1)
C = data[:,0]
A = data[:,1:]
 
cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)
 
for i in range(N):
  cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
  ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]
  
ok = np.all(ability >= X, axis=1)
 
x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)

Submission status: Accepted

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

cost = []

for i in range(2 ** N):
    skill = [0] * M
    total = 0
    for j in range(N):
        if (i >> j) & 1:
            for k in range(M):
                skill[k] += C[j][k + 1]
            total += C[j][0]
    flg = 1
    for sk in skill:
        if sk < X:
            flg = 0
    if flg == 1:
        cost.append(total)

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

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, m, x = map(int, input().split())
    ca = []
    for _ in range(n):
        tmp = list(map(int, input().split()))
        ca.append(tmp)
    ans = float('inf')
    for mask in range(1 << n):
        cost = 0
        algo = [0] * m

        for i in range(n):
            if 1 & (mask >> i):
                cost += ca[i][0]
                for j in range(1, m + 1):
                    algo[j - 1] += ca[i][j]
        ok = True
        for i in range(m):
            if algo[i] < x:
                ok = False
                break
        if ok:
            ans = min(ans, cost)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m, x = list(map(int, input().split()))
c = np.array([list(map(int, input().split())) for _ in range(n)])
pre = np.arange(n)
l = []
rem = []
ans = 0
for i in pre + 1:
    for j in itertools.combinations(pre, i):
        l.append(list(j))
for i in range(1, m + 1):
    for j, k in enumerate(l):
        ca = 0
        for ii in k:
            ca += c[ii, i]
        if ca < x:
            rem.insert(0, j)
        else:
            pass
    if len(rem) > 0:
        for j in rem:
            l.pop(j)
        rem = []
    if len(l) == 0:
        print(-1)
        break
else:
    for i in l:
        ca = 0
        for j in i:
            ca += c[j, 0]
        if ans == 0:
            ans = ca
        else:
            ans = min(ans, ca)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import itertools
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())

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

def inpl_str(): return list(sys.stdin.readline().split())

N, M, X = inpl()
books = list(list(map(int, input().split())) for _ in range(N))
ans = INF
for i in range(2**N):
    c = 0
    skill = [0]*M
    for j in range(N):
        if 1 << (j) & i:
            c += books[j][0]
            for k in range(M):
                skill[k] += books[j][k+1]
    if min(skill) >= X:
        ans = min(ans, c)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)
#10->n(sinhou)
def len_check(k,n):
    if len(k) == n:
        return k
    else:
        for _ in range(n-len(k)):
            k = '0'+k
        return k
#template
N,M,X = inputlist()
li = [0]*N
cost = 10**9
for i in range(N):
    li[i] = inputlist()
for k in range(2**N):
    ans = [0]*M
    k = len_check(base10to(k,2),N)
    lis = []
    tmp = 0
    count = 0
    for i in range(N):
        if k[i] == '1':
            lis.append(li[i])
    n = len(lis)
    for i in range(n):
        tmp += lis[i][0]
        alg = lis[i][1:]
        for j in range(M):
            ans[j] += alg[j]
    for i in range(M):
        if ans[i] >= X:
            count+=1
    if count == M:
        cost = min(cost,tmp)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
inf = 10**9
n, m, x = map(int, input().split())
a = [0] * n
c = [0] * n
y = [0] * n
for i in range(n):
    data = list(map(int, input().split()))
    c[i] = data[0]
    a[i] = data[1:]
ans = inf
for i in range(2**n):
    lis = [0]*n
    k = i
    money = 0
    know = [0] * m
    for j in range(n):
        if (k >> j) & 1:
            money += c[j]
            for l in range(m):
                know[l] += a[j][l]
    for z in know:
        if z < x:
            break
    else:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
Book = [list(map(int, input().split())) for _ in range(n)]
cost = [0 for _ in range(2**n)]
skill = [np.zeros(m) for _ in range(2**n)]
cost2 = []
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1:
            cost[i] += Book[j][0]
            skill[i] += np.array(Book[j])[1:m+1]
    if np.min(skill[i]) >= x:
        cost2.append(cost[i])
if cost2:
    print(min(cost2))
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
Book = [list(map(int, input().split())) for _ in range(n)]
cost = [0 for _ in range(2**n)]
skill = [np.zeros(m) for _ in range(2**n)]
cost2 = []
for i in range(2**n):
    for j in range(n):
        if (i >> j) & 1:
            cost[i] += Book[j][0]
            skill[i] += np.array(Book[j])[1:m+1]
    if np.min(skill[i]) >= x:
        cost2.append(cost[i])
if len(cost2) > 0:
    print(min(cost2))
else:
    print(-1)

Submission status: Accepted

Solution code:
import unittest
from io import StringIO
import sys


def resolve():
    n, m, x = [int(i) for i in input().split()]
    cc = []
    aa = []
    for comb in range(n):
        c, *a = [int(comb) for comb in input().split()]
        cc.append(c)
        aa.append(a)

    ans = float('inf')
    for comb in range(2**n):
        sum = 0
        xx = [0] * m
        for i in range(n):
            if (comb >> i) & 1:
                sum += cc[i]
                for j in range(m):
                    xx[j] += aa[i][j]
        for tx in xx:
            if tx < x:
                break
        else:
            ans = min(ans, sum)

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


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m, x = [int(k) for k in input().split()]
c = np.zeros(n, dtype=int)
a = np.zeros((n, m), dtype=int)
for i in range(n):
    c[i], *a[i] = [int(k) for k in input().split()]
cost = np.sum(c) + 1
for nn in range(1,n+1):
    for k in itertools.combinations(np.argsort(c),nn):
        k = list(k)
        cs = np.sum(c[k].flatten())
        if cs > cost:
            continue
        rikai = np.sum(a[k],axis=0)
        if np.all(rikai >= x):
            cost = min(cost,cs)
if cost < np.sum(c) + 1:
    print(cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
####処理を記述する箇所#####
import numpy as np

n,m,x = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
c = [a[i].pop(0) for i in range(n)]
ans = []
for s in range(1<<n):
    cost = 0
    mi = np.array([0]*m)
    for i in range(n):
        if (s>>i)&1:
            cost += c[i]
            mi += np.array(a[i])

    if np.all(mi >= x):
        ans.append(cost)
if ans:
    print(min(ans))
else:
    print('-1')

Submission status: Accepted

Solution code:
import copy

N, M, X = [int(x) for x in input().split()]

C = []
A = []

for i in range(N):
    _ = [int(x) for x in input().split()]
    C.append(_[0])
    A.append(_[1:])


def IsOver(a):
    return all([i >= X for i in a])


INT_MAX = 1000000000
res_min = INT_MAX


def dfs(b_list, index):
    if index is N:
        cost = 0
        a = [0] * M
        for i in range(N):
            if b_list[i]:
                cost += C[i]
                for j in range(M):
                    a[j] += A[i][j]
        if IsOver(a):
            global res_min
            res_min = min(res_min, cost)
        return

    for use in [True, False]:
        _tmp = copy.copy(b_list)
        _tmp.append(use)

        dfs(_tmp, index+1)


dfs([], 0)

print(str(res_min) if res_min is not INT_MAX else str(-1))

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
s=[list(map(int,input().split())) for i in range(N)]
t=[]
for i in range(1<<N):
  u=[0]*(M+1)
  for j in range(N):
    if ((i>>j)&1)==1:
      u=[u[k]+s[j][k] for k in range(M+1)] 
  for k in range(M):
    if u[k+1]<X:
      break
  else:
    t.append(u[0])
t.sort()
print(-1 if t==[] else t[0])

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
s=[list(map(int,input().split())) for i in range(N)]
t=[-1]
for i in range(1<<N):
  u=[0]*(M+1)
  for j in range(N):
    if ((i>>j)&1)==1:
      u=[u[k]+s[j][k] for k in range(M+1)] 
  for k in range(M):
    if u[k+1]<X:
      break
  else:
    if t==[-1]:
      t.clear()
    t.append(u[0])
t.sort()
print(t[0])

Submission status: Accepted

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

A =  []
S = [0 for _ in range(N)] 
min_value = 0 
score=[0 for _ in range(M)] 

for x in range(N):
  A.append(list(map(int,input().split())))

for x in range(N):
  min_value += A[x][0]


sucess = 0

for bit in range(2**N):
  for i in range(N):
    if (bit >> i) & 1:
      S.append(A[i][0])
      for x in range(M):
        score[x] += A[i][x+1]
  flag = 0
  #print(score)
  for k in score:
    if k >= X:
      flag += 1
    if flag ==len(score):
      #print("S",S)
      if min_value >= sum(S):
        min_value = sum(S)
        sucess += 1 
        
  score=[0 for _ in range(M)]
  S =[]
  
if sucess > 0:
	print(min_value)
else:
  print("-1")

Submission status: Accepted

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

A = [[] for _ in range(n)]
c = [0] * n

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

INF = 10**9
ans = INF
  
for s in range(0, 1 << n):
  skill = [0] * m
  money = 0
  for i in range(n):
    if(s >> i) % 2 == 0:continue
    money += c[i]
    for j in range(m):
      skill[j] += A[i][j]
  ok = True
  for j in range(m):
    if skill[j] < x:
      ok = False
  if ok:
    ans = min(ans, money)
    
if ans == INF:
  ans = -1
  
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
    if k == 0:
        b_list = np.asarray(b_list)
        x_list = np.dot(b_list, a_list)
        if np.all(x_list >= x):
            return np.inner(c_list, b_list)
        else:
            return ans
    ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
    ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
    return ans

n, m, x = map(int, input().split())
c_list = [] 
a_list = []
for i in range(0, n):
    c, *a = map(int, input().split())
    c_list.append(c)
    a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))

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

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

inf = int(1e20)
n, m, x = map(int, input().split())
_ = [[int(x) for x in input().split()] for _ in range(n)]
CA = np.array(_, dtype=int)
ans = inf
for indices in product([False, True], repeat=n):
    sums = np.sum(CA[np.array(indices)], axis=0)
    if min(sums[1:]) >= x:
        ans = min(ans, sums[0])
print(ans if ans != inf else '-1')

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
C=list()
A=list()
for i in range(n):
    X=list(map(int,input().split()))
    C.append(X[0])
    A.append(X[1:])
import itertools as it
V=list(it.product([0,1],repeat=n))
S=[10**7]*len(V)
for i in range(len(V)):
    Z=V[i]
    L=[0]*m
    for j in range(m):
        for k in range(n):
            L[j]+=A[k][j]*Z[k]
    if min(L)>=x:
        s=0
        for k in range(n):
           s+=C[k]*Z[k]
        S[i]=s
if  min(S)==10**7:
    print(-1)
else:
    print(min(S))

Submission status: Accepted

Solution code:
nmx = input('')
n = int(nmx.split(' ')[0])
m = int(nmx.split(' ')[1])
x = int(nmx.split(' ')[2])

clist=[]
alist=[]
for i in range(n):
    ca = input('')
    c = ca.split(' ')[0]
    clist.append(c)
    a = []
    for j in range(1,m+1):
        a.append(ca.split(' ')[j])
    alist.append(a)

min_price=99999999999
for i in range(2**n):
    skilllist=[0]*m
    buylist = [0]*n
    cost=0
    for j in range(n):
        if (i>>j )&1:
            buylist[j]=1
            cost+=int(clist[j])
            a = alist[j]
            for k in range(m):
                skilllist[k]+=int(a[k])

    ok = True
    for skill in skilllist:
        if skill < x:
            ok = False
    if ok and cost < min_price:
        min_price=cost
#    print('{}:\\{} :{} ->{} [{}]'.format(i,cost,buylist,skilllist,min_price))
if min_price == 99999999999:
    min_price=-1
print(min_price)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = [input() for i in range(N)]
result = 12 * 10**5 + 1
for i in range(1, 1 << N):
  cost = 0
  skill = [0 for i in range(M)]
  for j in range(N):
    if (i >> j) & 1:
      book = books[j].split()
      cost += int(book[0])
      for k in range(M):
        skill[k] += int(book[k + 1])
  if all(j >= X for j in skill):
    result = min(result, cost)
if result == 12 * 10**5 + 1:
  print(-1)
else:
  print(result)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA= [list(map(int,input().split())) for i in range(N)]
ans = float('inf')
for i in range(2**N):
    ci = 0
    lista = [0 for i in range(M)]
    for j in range(N):
        if (i >> j)&1 == 1:
            ci += CA[j][0]
            for k in range(M):
                lista[k] += CA[j][k+1]
    if min(lista) >= X:
        ans = min(ans,ci)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#k=int(input())
n,m,x=map(int,input().split())
#pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
al=[]
cl=[]
for i in range(n):
    l=list(map(int,input().split()))
    cl.append(l[0])
    al.append(l[1:])

price_list=[]
#bit全探索
for i in range(2**n):
    b=bin(i)
    score=[0 for k in range(m)]
    price=0

    for j in range(n):
        if ((i >> j) & 1):#二進数iの下から数えてj桁目が1か否か
            a=al[j]
            price+=cl[j]
            for k in range(m):
                score[k]+=a[k]
    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:
n, m, x = map(int, input().split())
c, all = [],[]
for _ in range(n):
  tmp = list(map(int, input().split()))
  c.append(tmp[0])
  all.append(tmp[1:])
ans = float('inf')
for bit in range(1, 1<<n):
  cost = 0
  totalA = [0]*m
  for i, al in enumerate(all):
    if (1<<i) & bit:
      for j, a in enumerate(al):
        totalA[j] += a
      cost += c[i]
  check = True
  for a in totalA:
    if a < x: check = False
  if check: ans = min(ans, cost)
if ans == float('inf'): print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
s = list(map(int, input().split()))
n = s[0]
m = s[1]
x = s[2]
book = []

for i in range(n):
    s = list(map(int, input().split()))
    book.append(s)
book=np.array(book)
ans=math.inf

for i in range(1<<n):

    skill = [0]*(m+1)
    for j in range(n):
        if i>>j & 1:
            for k,l in enumerate(book[j]):
                skill[k]+=l

    ok=True
    for j in range(1,m+1):
        if skill[j]<x :
            ok=False
            break
    if ok:
        ans=min(ans,skill[0])
if ans==math.inf:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
sup = [0]*n 
cost = [0]*n

for i in range(n):
  CA = list(map(int, input().split()))
  cost[i] = CA[0]
  sup[i] = CA[1:]
  
ans = -1

for i in range(2**n):
  skills = [0]*m
  c = 0
  for j in range(n):
    if i>>j&1:
      c += cost[j]
      for k in range(m):
        skills[k] += sup[j][k]
  if min(skills)>=x:
    if ans < 0:
      ans = c
    elif c<ans:
      ans = c
    
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
A = [[] for _ in range(n)]
cost = [0] * n
for i in range(n):
  c_as = list(map(int, input().split()))
  cost[i], A[i] = c_as[0], c_as[1:]
INF = 10**9
ans = INF
for s in range(0, 1 << n):
  smart = [0] * m
  cost_sum = 0
  for i in range(n):
    if (s >> i) % 2 == 0:
      continue
    cost_sum += cost[i]
    for j in range(m):
      smart[j] += A[i][j]
  ok = True
  for j in range(m):
    if smart[j] < x:
      ok = False
  if ok:
    ans = min(ans, cost_sum)
if ans == INF:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
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:])


INF = 10**9
ans = INF

for i in product([0,1], repeat=n):
    skill = [0] * m
    cost = 0
    for j in range(n):
        if i[j] == 1:
            for k in range(m):
                skill[k] += a[j][k]
            cost += c[j]
    if min(skill) >= x:
        ans = min(ans, cost)

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

Submission status: Accepted

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

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

maxi = 10 ** 5 * 12 + 1
ans = maxi

for bits in range(1, 2 ** n):
    scores = [0 for _ in range(m)]
    cost = 0
    for i in range(n):
        if bits >> i & 1:
            cost += arr[i][0]
            for j in range(m):
                scores[j] += arr[i][j + 1]

    if min(scores) >= x:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
INF = float("inf")

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

for bit in range(2 ** n):
    s = [0] * m
    cost = 0
    for i in range(n):
        if bit >> i & 1:
            cost += c[i]
            for j in range(m):    
                s[j] += a[i][j]
    if min(s) >= x:
        ans = min(cost, ans)

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

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(2 ** n):
    sum_ = [0] * m
    cost = 0
    for j in range(n):
        #sum_ = [0] * m
        if ((i >> j) & 1):
            cost += a[j][0]
            for k in range(m):
                sum_[k] += a[j][k + 1]
                
    flag = True
    for j in range(m):
        if sum_[j] < x:
            flag = False
    if flag:
        ans = min(ans, cost)
if ans == float('Inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
(n,m,x),*t=[[*map(int,t.split())]for t in open(0)]
m=M=9**9
for i in range(1,2**n):c,*a=map(sum,zip(*[t[j]for j in range(n)if i>>j&1]));m=min(m,M*(min(a)<x)or-~c)
print(m%M-1)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n,m,x = map(int,input().split())
a_list = []
price_list = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    price_list.append(tmp.pop(0))
    a_list.append(tmp)
    
all_list = [x for x in range(len(a_list))]
prices = []
for i in range(1,len(a_list)+1):
    for y in combinations(all_list,i):
        tmp = np.zeros(m)
        price = 0
        for ch in y:
            tmp += np.array(a_list[ch])
            price += price_list[ch]
        if np.all(tmp>=x):
            prices.append(price)
if prices != []:
    print(min(prices))
else:
    print(-1)

Submission status: Accepted

Solution code:
# DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF = 10 ** 9 + 100
ans = INF
def dfs(i, S, cost, C_list, A_list, N, M, X):
    global ans
    if i == N:
        ok = True
        for j in range(M):
            if S[j] < X:
                ok = False
                break
        if ok:ans = min(ans, cost)
        return
    dfs(i+1, S, cost, C_list, A_list, N, M, X)
    for j in range(M):
        S[j] += A_list[i][j]
    cost += C_list[i]
    dfs(i+1, S, cost, C_list, A_list, N, M, X)
    for j in range(M):
        S[j] -= A_list[i][j]
    cost -= C_list[i]
def main():
    global INF, ans
    N, M, X = map(int, input().split())
    C_list = []
    A_list = []
    for _ in range(N):
        C_A = list(map(int, input().split()))
        C_list.append(C_A[0])
        A_list.append(C_A[1:])
    S = [0 for _ in range(M)]
    cost = 0
    dfs(0, S, cost, C_list, A_list, N, M, X)
    if ans == INF:ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF = 10 ** 9 + 100
ans = INF
def dfs(i, S, cost, C_list, A_list, N, M, X):
    global ans
    # print(i, buy, cost, S)
    if i == N:
        ok = True
        for j in range(M):
            if S[j] < X:
                ok = False
                break
        if ok:ans = min(ans, cost)
        return
    dfs(i+1, S, cost, C_list, A_list, N, M, X)
    for j in range(M):
        S[j] += A_list[i][j]
    cost += C_list[i]
    dfs(i+1, S, cost, C_list, A_list, N, M, X)
    for j in range(M):
        S[j] -= A_list[i][j]
    cost -= C_list[i]
def main():
    global INF, ans
    N, M, X = map(int, input().split())
    C_list = []
    A_list = []
    for _ in range(N):
        C_A = list(map(int, input().split()))
        C_list.append(C_A[0])
        A_list.append(C_A[1:])
    S = [0 for _ in range(M)]
    cost = 0
    dfs(0, S, cost, C_list, A_list, N, M, X)
    if ans == INF:ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
(n,m,x),*t=[[*map(int,t.split())]for t in open(0)]
m=9**9
for i in range(1,2**n):
    c,*a=map(sum,zip(*[t[j]for j in range(n)if 1<<j&i]))
    if min(a)>=x:m=min(m,c+1)
print(m%9**9-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

INF = 10 ** 10

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    
    ans = INF

    for _ in range(N):
        CA = [int(i) for i in input().split()]
        C.append(CA.pop(0))
        A.append(CA)

    
    for n in range(2 ** N):
        flg = True
        cost = 0
        count = [0] * M
        for i in range(N):
            if n>>i & 1:
                for j in range(M):
                    count[j] += A[i][j]
                cost += C[i]
        # print(cost)
        # print(count)
        for j in range(M):
            if count[j] < X:
                flg = False
        if flg:
            ans = min(cost, ans)
    print(ans if ans != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = []
min_cost = float("inf")

for _ in range(N):
    books.append(list(map(int, input().split())))

for i in range(1, 2**N):
    i = format(i, '0{}b'.format(N))
    books_bought = [books[j] for j in range(N) if int(i[j])]
    cost = sum(book[0] for book in books_bought)
    experience = [sum(book[k] for book in books_bought) for k in range(1, len(books_bought[0]))]
    if sum(exp >= X for exp in experience) == M:
        min_cost = min(min_cost, cost)


if min_cost < float("inf"):
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

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


bits = [None] * N
ans = float('inf')

def f():
    global X
    global ans

    cost = 0
    algs = [0] * M
    for i in range(N):
        if bits[i]:
            book = A[i]
            cost += book[0]
            for i in range(1, M+1):
                algs[i-1] += book[i]
    # print(bits, algs, cost)
    p = True
    for ai in algs:
        if ai < X:
            p = False

    if p:
        ans = min(ans, cost)

def dfs(v):
    if v >= N:
        f()
        return

    bits[v] = True
    dfs(v+1)

    bits[v] = False
    dfs(v+1)

dfs(0)

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

Submission status: Accepted

Solution code:

import numpy as np
n, m, x = map(int, input().split())
refer = [list(map(int, input().split())) for _ in range(n)]

ans =[]
for i in range(2**n):
    skill = []
    money = 0

    for j in range(n):
        if (i >> j) & 1:
            skill.append(refer[j][1:])
            money += refer[j][0]
            a = np.array(skill)
            if np.all(np.sum(a, axis=0) >= x):
                ans.append(money)
if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

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

def solve():
    import sys
    import numpy as np

    N, M, X = list(map(int, sys.stdin.readline().split()))
    Cs = []
    AAs = []
    for _ in range(N):
        _in = list(map(int, sys.stdin.readline().split()))
        c, As = _in[0], _in[1:]
        Cs.append(c)
        AAs.append(np.array(As))

    ans = float("inf")
    for bit in range(2**N):
        total = 0
        masters = np.array([0]*M)

        for i in range(N):
            if bit>>i&1:
                total += Cs[i]
                masters += AAs[i]

            if sum(masters>=X) == M:
                ans = min(ans, total)

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
'''
参考
https://kakedashi-engineer.appspot.com/
https://note.com/sdestiny/n/nbd01567e6f7a
bit全探索を行う

※itertools.productについては以下を参照
https://note.nkmk.me/python-itertools-product/
'''
from itertools import product

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

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

INF = 10**9    # 解（参考書合計価格の最小値）と比較するために便宜上設定
ans = INF

# N冊の参考書すべてについて、
# 「買う=1」「買わない=0」の組み合わせ全パターン作成し
# それぞれの組み合わせについて
# 「合計価格は最小か」「理解度はX以上になるか」を調べる
# （bit全探索）
for p in product([0, 1], repeat=N):
    skill = [0] * M     # 参考書によって上げることのできる理解度（初期化）
    cost = 0            # 参考書の価格
    for n in range(N):
        if p[n]:    # N冊目の参考書を「買う」場合
            for m in range(M):
                skill[m] += A[n][m] # その参考書で上げられる理解度を加算
            cost += C[n]
    
    if min(skill) >= X:
        ans = min(ans, cost)

if ans == INF:
    print(-1)   # ans が更新されていない（目標達成できない）
else:
    print(ans)

Submission status: Accepted

Solution code:
#167C
def main():
    import itertools as ite
    import sys, numpy as np
    N,M,X = map(int, sys.stdin.readline().split())
    CA = [np.array(list(map(int, sys.stdin.readline().split()))) for _ in range(N)]
    bit = np.array(list(ite.product([0,1], repeat=N))) #式の展開
    #print(CA)
    #print(bit)
    ans = -1
    for row in bit:
        result = np.array([0 for _ in range(M+1)])
        #print(ans)
        for idx, num in enumerate(row):
            #print(CA[idx]*num)
            result += CA[idx]*num
        if np.all(result[1:]>=X):
            #print(result[0])
            if ans==-1 or ans >result[0]:
                ans = result[0]
    print(ans)
            
        


if __name__=='__main__':
    main()