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: Time Limit Exceeded

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()
from itertools import permutations
import numpy as np
def create_gen(string):
    for char in string: yield char
def main(): 
    N, M, X = MI()
    C = []; A = []; P = ''
    for i in range(N):
        tmp = LI()
        C.append(tmp[0]); A.append(tmp[1:]); P += str(i)
    origin_list = list(create_gen(P)); l = set()
    for i, _ in enumerate(origin_list, 1):
        for j in permutations(origin_list, r=i):
            l.add(j)
    c = {}
    for i in l: c[sum([C[int(j)] for j in i])] = i
    c = sorted(c.items(), key=itemgetter(0))
    for cost, i in c:
        r = np.zeros(M)
        for j in i: r += np.array(A[int(j)])
        if sum(r<X): continue
        else: print(cost); sys.exit()
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


def main():
    [N, M, X] = list(map(int, input().split()))

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, x = [int(i) for i in input().split(' ')]
c_s = []
a_s = []

for i in range(n):
  buf = [int(i) for i in input().split(' ')]
  c_s.extend(buf[:1])
  a_s.append(buf[1:])

choices = [i for i in range(n)]
min_result = [9999999,[]]

def list_add(a, b):
  ans = []
  for i in range(len(a)):
    ans.append(a[i]+b[i])
  return ans

def f(choice, und, money):
  if min(und) >= x:
    if money < min_result[0]:
      min_result[0] = money
      min_result[1] = list(set(choices)-set(choice))
    return
  
  if choice == []:
    return
    
  for i in range(len(choice)):
    f(choice[:i]+choice[i+1:], list_add(und, a_s[choice[i]]), money + c_s[choice[i]])
  return

f(choices, [0]*m, 0)
if min_result[1] == []:
  print('-1')
else:
  print(sum([c_s[i] for i in min_result[1]]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# l = list(range(0, n))
# print(l)

l = []
for i in range(n):
    l.append(list(map(int, input().split())))
    
# print(l)

min_value = -1
for v in itertools.permutations(l):
    lll = [0] * (m + 1)
    for ll in v:
        # print(ll)
        for i in range(len(ll)):
            lll[i] += ll[i]
        # print(lll)
        
        flag = True
        for i in range(len(lll)):
            if i == 0:
                continue
            if lll[i] < x:
                flag = False
        if flag == True:
            # print(lll)
            
            if min_value == -1:
                min_value = lll[0]
            elif min_value > lll[0]:
                min_value = lll[0]
                
            break
        
print(min_value)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
n, m, x = map(int, input().split())
C = [0] * n
A = [[0] * m for i in range(n)]


sumlist = [0] * m
for i in range(n):
    books = list(map(int, input().split()))
    C[i] = books[0]
    for j in range(m):
        A[i][j] = books[j + 1]
        sumlist[j] += books[j + 1]

# print(n, m, x)
# print(C)
# print(A)
# print(sumlist)

if min(sumlist) < x:
    print("-1")
    sys.exit(0)

def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

min_cost = sys.maxsize
for comb in itertools.permutations(range(n), n):
    learnlist = [0] * n
    cost = 0
    for i in comb:
        learnlist = python_list_add(learnlist, A[i])
        cost += C[i]
        if min(learnlist) >= x:
            if cost < min_cost:
                min_cost = cost
print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
N,M,x=map(int,input().split())
a=[]
for i in range(N):
    ai=list(map(int,input().split()))
    a.append(ai)
def cal(b):
    d=[]
    k=0
    c=0
    for i in range(M):
        d.append(0)
    for i in b:
        c+=a[i][0]
        for j in range(M):
            d[j]+=a[i][j+1]
    for i in d:
        if i<x:
            k=1
    if k==0:
        return c
    else:
        return 10000000

mini=10000000
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            for l in range(k,N):
                for m in range(l,N):
                    for n in range(m,N):
                        for o in range(n,N):
                            for p in range(o,N):
                                for q in range(p,N):
                                    for r in range(q,N):
                                        for s in range(r,N):
                                            for t in range(s,N):
                                                b={i,j,k,l,m,n,o,p,q,r,s,t}
                                                mini=min(mini,cal(b))

if mini==10000000:
    print(-1)
else: print(mini)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 

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

arr = []
cost = []

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

comb = list(permutations(range(0,n)))

min_cost = 10**20

for i in comb:
    total = 0
    new = [0]*m
    for j in i:
        total += cost[j]
        for k in range(m):
            new[k] += arr[j][k]
        flag = 0
        for k in range(m):
            if new[k]<x:
                flag = 1

        if flag==0:
            min_cost = min(min_cost, total)
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def func1(a,b,cl,mat,ans,m,n,x,a2):
    flag = 1
    for i in range(m):
        if a2[i]<x:
            flag=0
    if flag:
        ans[0]=min(a,ans[0])
    for i in range(b,n):
        for j in range(m):
            a2[j]+=mat[i][j]
        func1(a+cl[i],b+1,cl,mat,ans,m,n,x,a2)
        for j in range(m):
            a2[j]-=mat[i][j]

def main():
    n,m,x=MI()
    cl=[]
    mat =[]
    ans = [inf]
    a2=[0]*20
    for i in range(n):
        ls = LI()
        cl.append(ls[0])
        mat.append(ls[1:])
    func1(0,0,cl,mat,ans,m,n,x,a2)
    if ans[0]==inf:
        ans[0] = -1
    print(ans[0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,X = map(int,input().split())
book =[]
for x in range(N):
    A_list =  list(map(int, input().split()))
    book.append(A_list)
conbination =[]
for i, _ in enumerate(book, 1):     
    for j in itertools.permutations(book, r=i):  # rには1、2、3と渡される
        conbination.append(j)
minn =100000000
for x in conbination:
    A = [0]*M
    m = 0
    for y in x:
        for z in range(len(y)):
            if z ==0:
                m +=y[z]
            else:
                A[z-1] +=y[z]
    if minn >m and X<=min(A):
        
        minn =m
        
if minn != 100000000:
    print(minn)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

sums = [0] * M
able = True
for a in A:
    for i in range(M):
        sums[i] += a[i+1]

for s in sums:
    if s < X:
        able = False

if not able:
    print('-1')
    exit()


import itertools
P = list(itertools.permutations(range(len(A))))

res = float('inf')

for p in P:
    x = [0] * M
    price = 0
    for _p in p:
        a = A[_p]
        price += a[0]
        for i in range(1, len(a)):
            x[i-1] += a[i]
        flg = True
        for _x in x:
            if _x < X:
                flg = False
                break
        if flg:
            res = min(res, price)
            break


print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    lis = [i for i in range(N)]
    ans = []
    for c in itertools.combinations_with_replacement(lis,N):
        tmp = 0
        dic = {key:0 for key in range(M)}
        for i in set(c):
            tmp += C[i]
            for n,a in enumerate(A[i]):
                dic[n] += a
        for m in range(M):
            if(dic[m] < X):
                break
        else:
            ans.append(tmp)
    return min(ans) if(ans != []) else -1
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    # solve()
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    lis = [i for i in range(N)]
    ans = []
    for k,_ in enumerate(lis,1):
        for c in itertools.permutations(lis,r=k):
            tmp = 0
            dic = {key:0 for key in range(M)}
            for i in set(c):
                tmp += C[i]
                for n,a in enumerate(A[i]):
                    dic[n] += a
            for m in range(M):
                if(dic[m] < X):
                    break
            else:
                ans.append(tmp)
    return min(ans) if(ans != []) else -1
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    # solve()
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]
P = permutations(books, len(books))
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break

if ans == 10 ** 9 + 1:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
V=[]
ok=[]
for i in range(1,n+1):
    for v in itertools.permutations(L,i):
        V.append(v)
for i in range(len(V)):
    cost=0
    error=0
    for k in range(m):
        sm=0
        for j in V[i]:
            sm += j[k+1]
        if sm<x:
            error += 1
    if error==0:
        for j in V[i]:
            cost += j[0]
        ok.append(cost)
ok.sort()
if len(ok)>0:
    print(ok[0])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, M, K = map(int, input().split())
Q = [np.asarray(input().split(), dtype=int) for i in range(N)]
min_cost = 10**9
for q in itertools.permutations(Q):
  cost = 0
  C = np.zeros(M)
  for i in q:
    cost += i[0]
    C = C + i[1:]
    if (C >= K).all():
      min_cost = min([cost, min_cost])
      break
print(min_cost) if min_cost != 10**9 else print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools

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

li = deque()

sum = -1
ans = 0
for i in range(n):
    li.append(list(map(int, input().split())))

for i in range(1,n+1):
    for v in itertools.permutations(li, i):
        ok = True
        for j in range(1,m+1):
            ans = 0
            for k in v:
                ans += k[j]
                if ans >= x:
                    break
            if ans < x:
                ok = False
                break

        if ok == True:
            s=0
            for j in range(i):
                s+=v[j][0]
            if sum > s or sum == -1:
                sum=s


print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

N,M,X = [int(i) for i in input().split()]
A = np.array([[int(i) for i in input().split()]])
for _ in range(N-1):
    B = np.array([int(i) for i in input().split()])
    A = np.vstack([A, B])

m = min([np.sum(A[:,i:i+1]) for i in range(1,M+1)])
if m < X:
    print(-1)
    exit()

ans = np.sum(A[:,0:1])
q = deque([[i] for i in range(N)])
while len(q) != 0:
    L = q.pop()
    L.sort(reverse=True)
    B = A.copy()
    for i in L:
        B = np.delete(B, i, 0)
    m = min([np.sum(B[:,i:i+1]) for i in range(1,M+1)])
    if m < X:
        continue
    ans = min([ans,np.sum(B[:,0:1])])
    for i in range(N):
        L1 = L.copy()
        L1.append(i)
        L1set = set(L1)
        if len(L) < len(L1set):
            q.append(L1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, X = map(int, input().split())
books = []
for _ in range(N):
    books.append(list(map(int, input().split())))
P = permutations(books, len(books))
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break

if ans == 10 ** 9 + 1:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, X = map(int, input().split())
C = []
A = dict()
for i in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    for j in range(1, M+1):
        if j in A:
            A[j].append(CA[j])
        else:
            A[j] = [CA[j]]

cost = float("inf")

for i in range(1, N+1):
    for pm in itertools.permutations(list(range(1, N+1)), r=i):
        c = 0
        k = dict()
        for p in pm:
            c += C[p-1]

            for m in range(1, M+1):
                if m in k:
                    k[m] += A[m][p - 1]
                else:
                    k[m] = A[m][p - 1]

        if min(k.values()) >= X:
            cost = min(cost, c)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

N,M,X = [int(i) for i in input().split()]
A = np.array([[int(i) for i in input().split()]])
for _ in range(N-1):
    B = np.array([int(i) for i in input().split()])
    A = np.vstack([A, B])

m = min([np.sum(A[:,i:i+1]) for i in range(1,M+1)])
if m < X:
    print(-1)
    exit()

ans = np.sum(A[:,0:1])
q = deque([[i] for i in range(N)])
while len(q) != 0:
    L = q.pop()
    L.sort(reverse=True)
    B = A.copy()
    for i in L:
        B = np.delete(B, i, 0)
    m = min([np.sum(B[:,i:i+1]) for i in range(1,M+1)])
    if m < X:
        continue
    ans = min([ans,np.sum(B[:,0:1])])
    for i in range(N):
        L1 = L.copy()
        L1.append(i)
        L1set = set(L1)
        if len(L) < len(L1set):
            q.appendleft(L1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#n = int(input())
n,m,x = map(int,input().split())
#a_L = list(map(int,input().split()))
import itertools
L = list(itertools.permutations(list(range(0,n))))
#print(L)
a_L = []
c_L = []

import numpy as np

def check_L(L,x):
    flag = True
    for i in range(len(L)):
        if L[i] < x:
            flag = False
    return flag
        

for i in range(n):
    tmp= list(map(int,input().split()))
    c = tmp[0]
    tmpL = tmp[1:]
    a_L.append(tmpL)
    c_L.append(c)

ans_price = float("inf")
for z in L:
    ans_L = np.array([0 for i in range(m)])
    price = 0
    for i in z:
        price += c_L[i]
        ans_L += a_L[i]
        if check_L(ans_L,x):
            ans_price = min(ans_price,price)
            break
if ans_price == float("inf"):
    print(-1)
else:
    print(ans_price)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, X = map(int, input().split())
c_list = []
for _ in range(N):
  c_list.append(list(map(int, input().split())))
  
cand = []
e_list = [i for i in range(N)]
for e in itertools.combinations_with_replacement(e_list, N):
  sum_list = np.zeros(M)
  sum_maney = 0
  for i in set(e):
    sum_list += np.array(c_list[i][1:])
    sum_maney += c_list[i][0]
  flag = True
  for m in range(M):
    if not sum_list[m] >= X:
      flag = False
  if flag:
    cand.append(sum_maney)
if cand == []:
  print(-1)
else:
  print(min(cand))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 

n,m,x = [int(x) for x in input().strip().split()]

cost = []
mat = []
res = 10**20

tot = [0 for i in range(m)]

for i in range(n):
    arr = [int(x) for x in input().strip().split()]
    cost.append(arr[0])
    mat.append(arr[1:])
    tot = [tot[i]+arr[i] for i in range(m)]

flag=True
for to in tot:
    if to<x:
        flag=False
        break

if flag is False:
    print(-1)
else:
    perm = permutations([i for i in range(n)]) 

    for p in list(perm): 
        rem = [x for i in range(m)]
        comp = set([])
        curr_cost = 0
        for i in p:
            if len(comp)==m:
                break
            curr_cost+=cost[i]
            for j in range(m):
                rem[j]-=mat[i][j]
                if rem[j]<=0:
                    comp.add(j)

        if len(comp)==m:
            res = min(res,curr_cost)

    if res==10**20:
        res=-1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, K = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(N)]
min_cost = 10**9
for q in itertools.permutations(Q):
  cost = 0
  C = [0] * M
  for i in q:
    cost += i[0]
    for j,c in enumerate(i[1:]):
      C[j] += c
    if len([c for c in C if c >= K]) == M:
      min_cost = min([cost, min_cost])
      break
print(min_cost) if min_cost != 10**9 else print(-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 

n,m,x = [int(x) for x in input().strip().split()]

cost = []
mat = []
res = 10**20

for i in range(n):
    arr = [int(x) for x in input().strip().split()]
    cost.append(arr[0])
    mat.append(arr[1:])

perm = permutations([i for i in range(n)]) 

for p in list(perm): 
    rem = [x for i in range(m)]
    comp = set([])
    curr_cost = 0
    for i in p:
        if len(comp)==m:
            break
        curr_cost+=cost[i]
        for j in range(m):
            rem[j]-=mat[i][j]
            if rem[j]<=0:
                comp.add(j)

    if len(comp)==m:
        res = min(res,curr_cost)

if res==10**20:
    res=-1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, K = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(N)]
min_cost = 10**9
for q in itertools.permutations(Q):
  cost = 0
  C = [0] * M
  for i in q:
    cost += i[0]
    for j,c in enumerate(i[1:]):
      C[j] += c
    if len([c for c in C if c >= K]) == M:
      min_cost = min([cost, min_cost])
      break
print(min_cost) if min_cost != 10**9 else print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import defaultdict
from itertools import permutations

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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

ans = INF
for combination in permutations(range(N), N):
    A = defaultdict(int)
    cost = 0
    for c in combination:
        book = books[c]
        cost += book[0]
        for i in range(1, M + 1):
            A[i] += book[i]
        ok = True
        for i in range(1, M + 1):
            if A[i] < X:
                ok = False
                break
        if ok:
            ans = min(ans, cost)

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

Submission status: Time Limit Exceeded

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

junretu = itertools.permutations(range(n))
min_nedan = 10**9
for j in junretu:
  count_list = [0]*m
  nedan = 0
  for b in j:
    naiyou = book[b]
    nedan += naiyou[0]
    for i in range(1, m+1):
      count_list[i-1] += naiyou[i]
    if min(count_list)>=x:
      break
  else:
    print(-1)
    exit()
  if nedan < min_nedan:
    min_nedan = nedan
print(min_nedan)

Submission status: Time Limit Exceeded

Solution code:
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

def check(tisiki):
    cnt = 0
    for t in tisiki:
        if t<X:
            return False
    return True

ans = 10**9
for v in permutations(list(range(N))):
    tisiki = [0] * M
    cost = 0
    for i in v:
        b = book[i]
        cost += b[0]
        for t in range(M):
            tisiki[t] += b[t+1]
        
        if check(tisiki):
            ans = min(ans, cost)
            break

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m, x = map(int, input().split())
c = []
ans = []
for _ in range(n):
    l = list(map(int, input().split()))
    c.append(l)

for i in range(1, n+1):
    for vl in itertools.permutations(c, i):
        a = [0] * m
        p = 0
        for v in vl:
            p += v[0]
            for j in range(m):
                a[j] += v[1+j]
        flag = True
        for k in range(m):
            if a[k] < x:
                flag = False
        if flag:
            ans.append(p)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Time Limit Exceeded

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

junretu = itertools.permutations(range(n))
min_nedan = 10**9
for j in junretu:
  count_list = [0]*m
  nedan = 0
  for b in j:
    naiyou = book[b]
    nedan += naiyou[0]
    for i in range(1, m+1):
      count_list[i-1] += naiyou[i]
    if min(count_list)>=x:
      break
  else:
    print(-1)
    exit()
  if nedan < min_nedan:
    min_nedan = nedan
print(min_nedan)

Submission status: Time Limit Exceeded

Solution code:
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

def check(tisiki):
    cnt = 0
    for t in tisiki:
        if t<X:
            return False
    return True

ans = 10**9
for v in permutations(list(range(N))):
    tisiki = [0] * M
    cost = 0
    for i in v:
        b = book[i]
        cost += b[0]
        for t in range(M):
            tisiki[t] += b[t+1]
        
        if check(tisiki):
            ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from copy import deepcopy

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

CAS = [[int(i) for i in input().split()] for _ in range(N)]


ok = False
mi = [float('inf'), *[0]*(M)]

for i in range(2**N):
  t = [0]*(M+1)
  for j in range(N):
    if (i >> j) & 1:
      t = [a+b for a, b in zip(CAS[j], t)]

  if all(a >= X for a in t[1:]) and mi[0] > t[0]:
    mi = t
    ok = True


if ok:
  print(mi[0])
else:
  print(-1)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

CAS = [[int(i) for i in input().split()] for _ in range(N)]


ok = False
mi = [float('inf'), *[0]*(M)]

fs = '{:0' + str(N) + 'b}'

for i in range(2**N):
  s = fs.format(i)
  t = [0]*(M+1)
  for i, f in enumerate(s):
    if f == '1':
      t = [a+b for a, b in zip(CAS[i], t)]

  if all(a >= X for a in t[1:]) and mi[0] > t[0]:
    mi = t
    ok = True


if ok:
  print(mi[0])
else:
  print(-1)

Submission status: Accepted

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

inf=10**18
ans=inf

limit=2**n
for bit in range(1,limit):
    sum=[0 for i in range(m)]
    cost=0
    for i in range(n):
        if (1<<i & bit):
            cost+=c[i]
            for j in range(m):
                sum[j]+=arr[i][j]
    flag=1
    for i in range(m):
        if sum[i]<x:
            flag=0
            break
    if flag==0:
        continue
    ans=min(ans,cost)
if ans!=inf:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]
MAX_ANS = 10**9
ans = MAX_ANS

for i in range(2 ** N):
    buy = []
    for j in range(N):
        if (i >> j) & 1:
            buy.append(j)

    understand = [0] * (M + 1)
    money = 0
    for b in buy:
        money += CA[b][0]
        for i in range(1, M + 1):
            understand[i] += CA[b][i]

    isok = True
    for i in range(1, M + 1):
        if understand[i] < X:
            isok = False
            break

    if isok:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m, x = list(map(int, readline().split()))
    c = [list(map(int, readline().split())) for _ in range(n)]
    mv = 10 ** 10
    for v in itertools.product([True, False], repeat=n):
        score = [0] * m
        amt = 0
        for i, vv in enumerate(v):
            if vv:
                amt += c[i][0]
                for j in range(m):
                    score[j] += c[i][j+1]
                b = True
                for sv in score:
                    if sv < x:
                        b = False
                        break
                if b:
                    mv = min(mv, amt)
    print(mv if mv != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[list(map(int,input().split(" "))) for i in range(n)]
ans=[]
for i in range(1<<n):
    cond = [0]*n
    for j in range(n):
        if 1&(i>>j):
            cond[j] = 1
    count=[0]*(m+1)
    for k in range(n):
        if cond[k]==1:
            for s in range(m+1):
                count[s]+=l[k][s]
    flag=0
    for a in range(1,m+1):
        if count[a]<x:
            flag=1
            break
    if flag==0:
        ans.append(count[0])
if ans==[]:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

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

for i in range(N):
    CA = list(map(int, input().split()))
    lis.append(CA)

ans = 1e9
for i in range(2 ** N):
    check = [0 for i in range(M + 1)]
    for j in range(N):
        if i >> j & 1:
            for k in range(M + 1):
                check[k] += lis[j][k]
        if min(check[1:]) >= X:
            ans = min(ans, check[0])
if ans == 1e9:
    print(-1)
else:
    print(ans)