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: Wrong Answer

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

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

ans = 10**18
for i in range(2**N):
    d = [0]*M
    cst = 0
    for j in range(N):
        if (i>>j&1):
            cst += C[j]
            for s in range(M):
                d[s] += A[j][s]

    for j in d:
        if j < X:
            break
        else:
            ans = min(ans,cst)

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

Submission status: Wrong Answer

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N,M,X = LI()
B = [LI() for _ in range(N)]
C = []
A = []
S = [0] * M
pri = []
T = [X] * M

for ind,b in enumerate(B):
	C.append(b[0])
	tmp = [ind,0]
	for i,v in enumerate(b[1:]):
		S[i]+=v
		tmp[1]+=v
	tmp[1]/=b[0]
	pri.append(tmp[::])
#print(S)
for s in S:
	if s < X:
		print("-1")
		exit(0)

pri.sort(key=lambda x:x[1], reverse=True)
#print(pri)

money = 0
sind = 0
while True:
	tmp = pri[sind]
	ind = tmp[0]
	flg = True
	for i in range(len(T)):
		T[i]-=B[ind][i+1]
		if T[i] > 0:
			flg = False
	money+=B[ind][0]
	if flg:
		print(money)
		break
	sind+=1

Submission status: Wrong Answer

Solution code:
n,m,x = map(int,input().split())
li=[input() for i in range(n)]
li2 = []
for i in range(n):
    li2.append( [int(x.strip()) for x in li[i].split()])
    
ans = 10**7

for i in range(2 ** n):
    res = ""
    b = str(format(i, '012b')) #2進数に変換
    a = [0]*(m+1)
    for j in range(n):
        if b[-1-j] == "1":
            a = [x1 + x2 for (x1, x2) in zip(a, li2[j])]
           # print(a)
            
    c = len([j for j in a[1:] if j>=x])
    if c ==m and ans>a[0]:
        
        ans = a[0]
        #print(ans)

print(ans)

Submission status: Wrong Answer

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

c=[0]*n
a=[[] for _ in range(n)]
for i in range(n):
    tem=list(map(int,input().split()))
    c[i]=tem[0]
    a[i]=tem[1:]
    
ans=10*20

for i in range(2**n):
    aaa=[0]*m
    money=0
    for j in range(n):
        if (i>>j)&1:
            money+=c[j]
            for k in range(m):
                aaa[k]+=a[j][k]
    if min(aaa)>=x:
        ans=min(ans,money)
if ans<10*20:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  sum = 0
  
  for i in range(1,m):
    p = 0
    for e in pair:
      p += e[i]
    
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
list = [] 
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
      
  sum = check(pair,m,x)
  if(sum != -1):
    list.append(sum)
    
if(len(list) == 0):
  print(-1)
else:
  vmin = min(list)
  print(vmin)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  sum = 0
  
  for i in range(1,m):
    p = 0
    for e in pair:
      p += e[i]
    
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
      
  sum = check(pair,m,x)
  if sum != -1:
    if min == -1:
      min = sum
    elif min > sum:
      min = sum
    
print(min)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p = 0
    for j in range(l):
      p += pair[j][i]
    
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
      
  sum = check(pair,m,x)
  if sum != -1:
    if min == -1:
      min = sum
    elif min > sum:
      min = sum
    
print(min)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p = 0
    for j in range(l):
      p += pair[j][i]
    if(p < x):
      return -1
    
  for i in range(l):
    sum += pair[i][0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
  sum = check(pair,m,x)
  
  if sum != -1:
    if min == -1:
      min = sum
    elif min > sum:
      min = sum
    
print(min)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p= 0
    for j in range(l):
      p += pair[j][i]
    if(p < x):
      return -1
    
  for i in range(l):
    sum += pair[i][0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
  sum = check(pair,m,x)
  
  if min == -1:
    min = sum
  elif sum != -1 and min > sum:
    min = sum
    
print(min)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p= 0
    for j in range(l):
      p += pair[j][i]
    if(p < x):
      return -1
    
  for i in range(l):
    sum += pair[i][0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
  sum = check(pair,m,x)
  if min == -1 and sum >= 0:
    min = sum
  elif sum != -1 and min > sum:
    min = sum
    
print(min)

Submission status: Wrong Answer

Solution code:
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p= 0
    for j in range(l):
      p += pair[j][i]
    if(p < x):
      return -1
    
  for i in range(l):
    sum += pair[i][0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
  sum = check(pair,m,x)
  if min == -1 and sum >= 0:
    min = sum
  elif min > sum:
    min = sum
    
print(min)

Submission status: Wrong Answer

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

mc = 100001
k = [0 for _ in range(n)]

def search(i, cost, k):
    if i == n:
        return cost if min(k) >= x else mc
    else:
        return min(search(i + 1, cost + b[i][0], [k[idx] + b[i][1][idx] for idx in range(m)]), search(i + 1, cost, [e for e in k]))

ans = search(0, 0, [0 for _ in range(m)])
if ans == mc:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def bitsearch(n, a, x):
  mincost = 10**10
  for b in range(2**n):
    bit = format(b, f"0{n}b")
    total = [sum([int(bit[i])*a[i][j] for i in range(n)]) for j in range(m+1)]
    if min(total[1:]) >= x:
      mincost = min(mincost, total[0])
  return mincost

n, m, x = map(int, input().split())
a = []
for i in range(n):
  line = list(map(int, input().split()))
  a.append(line)
print(bitsearch(n, a, x))

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
clist = []
nums = []
cost = 0
total = []
ans = 0
c = []

for i in range(n):
  clist.append(list(input().split())) 
    
for i in range(2 ** n):
  num = [0] * n
  cost  = [0] * n
  book = [0] * m
  check = 'OK'
  for j in range(n):
    if ((i >> j) & 1):
      num[j] = 1
      cost[j] = int(clist[j][0])
      for k in range(1,m+1):
        book[k-1] += int(clist[j][k])
  if min(book) >= x:
      for i in cost:
        ans += i
      c.append(ans)
      ans = min(c)  
  else:
    check = 'NG'
        
if check == 'NG':
  print('-1')
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys,itertools
N,M,X=map(int,input().split())
ALL=[]
cost=0
for i in range(N):
  listA=list(map(int,input().split()))
  ALL+=[listA]
  cost+=listA[0]
for i in range(1,M+1):
  SUM=0
  for k in range(N):
    SUM+=ALL[k][i]
  if SUM<X:
    print(-1)
    sys.exit()
cost2=10**9    
for take in range(1,N+1):
  takeL=list(itertools.combinations(list(range(N)),take))
  for t in takeL:
    for i in range(1,M+1):
      SUM=0
      cost3=0
      for k in range(take):
        SUM+=ALL[t[k]][i]
        cost3+=ALL[t[k]][0]
      if SUM<X:
        break
      if i==M-1:
        cost2=min(cost2,cost3)
print(cost2)

Submission status: Wrong Answer

Solution code:
import sys,itertools
N,M,X=map(int,input().split())
ALL=[]
cost=0
for i in range(N):
  listA=list(map(int,input().split()))
  ALL+=[listA]
  cost+=listA[0]
for i in range(1,M+1):
  SUM=0
  for k in range(N):
    SUM+=ALL[k][i]
  if SUM<X:
    print(-1)
    sys.exit()
cost2=10**7    
for take in range(1,N+1):
  takeL=list(itertools.combinations(list(range(N)),take))
  for t in takeL:
    for i in range(1,M+1):
      SUM=0
      cost3=0
      for k in range(take):
        SUM+=ALL[t[k]][i]
        cost3+=ALL[t[k]][0]
      if SUM<X:
        break
      if i==M-1:
        cost2=min(cost2,cost3)
print(cost2)

Submission status: Wrong Answer

Solution code:
import sys
N,M,X=map(int,input().split())
ALL=[]
cost=0
for i in range(N):
  listA=list(map(int,input().split()))
  ALL+=[listA]
  cost+=listA[0]
for i in range(1,M+1):
  SUM=0
  for k in range(N):
    SUM+=ALL[k][i]
  if SUM<X:
    print(-1)
    sys.exit()
ALL.sort(reverse=True)
cost2=0
for start in range(1,N):
  for i in range(M+1):
    SUM=0
    for k in range(start,N):
      SUM+=ALL[k][i]
    if SUM<X:
      print(cost-cost2)
      sys.exit()
  cost2+=ALL[start-1][0]

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(n)]
 
import itertools as it
import math
 
cost = math.inf
for comb in it.chain(*(it.combinations(C, r) for r in range(1, n+1))):
    print(comb)
    print(*comb)
    c, *a = map(sum, zip(*comb))
    print(c,a)
    if c < cost and min(a) >= x:
        cost = c
 
print(-1 if cost is math.inf else cost)

Submission status: Wrong Answer

Solution code:
import math
def main():
    N,M,X = map(int, input().split())
    C = [0 for j in range(N)]
    A = [[0 for j in range(M)] for i in range(N)]
    for i in range(0, N):
        l = list(map(int, input().split()))
        
        C[i] = l[0]
        A[i] = l[1:]

    res = max(C)*N
    possible = False
    for i in range(0,1<<N):
        cost= 0
        und= [0 for j in range(M)]
        for j in range(0,N):
            if (i>>j)&1 == 1:
                cost += C[j]
                und =list(map(lambda x,y: x+y, und, A[j]))
        
        if min(und) - X >=0 and cost < res:
            res = cost
            possible = True

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(2**n):
    amt = 0
    algo = [0]*m
    for j in range(m+1):
        if (i>>j)&1:
            amt += li[j][0]
            book = li[j]
            for k, value in enumerate(book[1:]):
                algo[k] += value

    if min(algo) >= x:
        if amt < ans:
            ans = amt
    
if ans == 10**7:
    print("-1")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    n,m,r = map(int, input().split())
    dn = [[0] * m for _ in range(n)]
    
    for i in range(n):
        dn[i][:] = map(int, input().split())

    dn = np.array(dn)
    cost = []
    sh = 0
    inf = 10e8
    cost = inf
    k = np.zeros(m+1)
    
    def secom(j,k,cost):
        if j == n:
            
            if np.all(k>=r):
                print(k)
                cost = min(cost,k[0])
                return cost
            else:
                return cost
        
        cost1 = secom(j+1,k,cost)
        k += dn[j]
        cost2 = secom(j+1,k,cost)
        k -= dn[j]
        
        return min(cost1,cost2)
    
    
    cost = secom(0,k,cost)
    if cost == inf:
        print(-1)
    else:
        print(int(cost))
        
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
def main():
    n,m,r = map(int, input().split())
    d = [[0] * m for _ in range(n)]
    for i in range(n):
        d[i][:] = map(int, input().split())

    dn = np.array(d)
    cost = []
    sh = 0
    inf = 10e8
    cost = inf
    k = np.zeros(m+1)
    
    def secom(j,k,cost):
        if j == n:
            
            if np.all(k>=r):
                cost = min(cost,k[0])
                return cost
            else:
                return cost
        
        cost1 = secom(j+1,k,cost)
        k += dn[j]
        cost2 = secom(j+1,k,cost)
        k -= dn[j]
        
        return min(cost1,cost2)
    
    
    cost = secom(0,k,cost)
    if cost == inf:
        print(-1)
    else:
        print(int(cost))
        
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
def main():
    n,m,r = map(int, input().split())
    d = [[0] * m for _ in range(n)]
    for i in range(n):
        d[i][:] = map(int, input().split())

    dn = np.array(d)
    cost = []
    sh = 0
    inf = 10e8
    cost = inf
    k = np.zeros(m+1)
    
    def secom(j,k,cost):
       # print(k)
        if j == n:
            
            if np.all(k>=r):
                cost = min(cost,k[0])
                return cost
            else:
                return cost
        
        cost1 = secom(j+1,k,cost)
        k += dn[j]
        cost2 = secom(j+1,k,cost)
        k -= dn[j]
        
        return min(cost1,cost2)
    
    cost = secom(0,k,cost)
    print(int(cost))
        
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    A[i] = temp[1:]

def solve():
    ans = float('inf')
    # Total: O(2^N*N*M)
    total = 1 << N
    for mask in range(total):  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        
        for i in range(N):  #O(N)
            if (mask >> i) & 1:
                cost += C[i]
                for j in range(M): #O(M)
                    L[j] += A[i][j]
            
        ok = True
        for i in range(M):
            if L[i] < X: 
                ok = False
        print(L, cost, ok)
        if ok:
            ans = min(ans,cost)

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict
N, M , X = map(int, input().split())
C = [0 for i in range(N)]
D = defaultdict(list)


for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    D[C[i]] = temp[1:]

def solve():
    ans = 12345678
    combs = []
    for i in range(N+1):
        combs.extend(combinations(C,i))

    # Total: O(2^N*N*M)
    count = 0
    for comb in combs:  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        

        for k in comb:  #O(N)
            cost += k
            for i in range(M): #O(M)
                L[i] += D[k][i]
        #print(comb, L, cost)
        ok = True
        for i in range(M):
            if L[i] < X: 
                ok = False
            
        if ok:
            ans = min(ans,cost)

        count += 1
    #print(count)
    if ans == 12345678:
        print(-1)
    else:
        print(ans)
solve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict
N, M , X = map(int, input().split())
C = [0 for i in range(N)]
D = defaultdict(list)
ans = 12345678

for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    D[C[i]] = temp[1:]

def solve():
    global ans
    combs = []
    for i in range(N+1):
        combs.extend(combinations(C,i))

    # Total: O(2^N*N*M)
    for comb in combs:  #O(2^N)
        L = [0 for i in range(M)]
        cost = 0
        ok = True

        for k in comb:  #O(N)
            cost += k
            for i in range(M): #O(M)
                L[i] += D[k][i]
        print(comb, L, cost)
        for i in range(M):
            if L[i] < X: 
                ok = False
            
        if ok:
            ans = min(ans,cost)

    if ans == 12345678:
        print(-1)
    else:
        print(ans)
solve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict
N, M , X = map(int, input().split())
C = [0 for i in range(N)]
D = defaultdict(list)
ans = float('inf')

for i in range(N):
    temp = list(map(lambda x:int(x), input().split()))
    C[i] = temp[0]
    D[C[i]] = temp[1:]

def solve():
    global ans
    combs = []
    for i in range(N+1):
        combs.extend(combinations(C,i))

    # Total: O(2^N*N*M)
    for comb in combs:  #O(2^N)
        L = [0 for i in range(M)]
        count = 0
        ok = True

        for k in comb:  #O(N)
            count += k
            for i in range(M): #O(M)
                L[i] += D[k][i]
        
        for i in range(M):
            if L[i] < X: 
                ok = False
            
        if ok:
            ans = min(ans,count)

    return ans if ans != float('inf') else -1
print(solve())

Submission status: Wrong Answer

Solution code:
n,m,x=map(int,input().split())
a=[]
for c in range(n):
    a.append([int(x) for x in input().split()])
s=10**5+1
for d in range(2**n):
    p=0
    q=[0]*m
    for e in range(n):
        if (d%(2**(e+1)))//(2**e)==1:
            p+=a[e][0]
            for f in range(m):
                q[f]+=a[e][f+1]
    if s<p:
        continue
    r=0
    for f in range(m):
        if q[f]<x:
            r=1
            break
    if r==0:
        s=p
if s==10**5+1:
    print(-1)
else:
    print(s)

Submission status: Wrong Answer

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

posibilities = []

for _ in range(n):
    book = list(map(int, input().split()))
    b = posibilities[:]
    for i in b:
        posibilities.append([z+y for z, y in zip(i, book)])
    posibilities.append(book)

posibilities.sort(key=lambda i: i[0])

left = -1
right = len(posibilities)-1

while right-left > 1:
    mid = (left+right)//2
    for i in posibilities[mid][1:]:
        if i < x:
            left = mid
            break
    else:
        right = mid

for i in posibilities[right]:
    if i < x:
        print(-1)
        break
else:
    print(posibilities[right][0])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,m,x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

ans = 10**9
for i in range(1, n+1):
  for j in combinations(ca,i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    if all(t[num] >= x for num in range(1,m)):
      ans = min(ans, t[0])

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

Submission status: Wrong Answer

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

p = []
u = []

for i in range(N):
  t = list(map(int, input().split()))
  p.append(t[0])
  u.append(t[1:])

candidate = []
for i in range(1, M+1):
  for comb in itertools.combinations(range(N), i):
    price = 0
    understand = [0]*M
    for j in range(i):
      price += p[comb[j]]
      understand = [x + y for (x, y) in zip(understand, u[comb[j]])]
    if all(elem >= X for elem in understand):
      candidate.append(price)

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

Submission status: Wrong Answer

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

A=[[] for _ in range(n)] #Aでn個
c=[0]*n #c={0,0,...,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(1<<n):
    smart=[0]*m
    cost_sum=0
    for i in range(n):
        if (s>>i)==0:
            continue
        cost_sum+=c[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: Wrong Answer

Solution code:
def solve(string):
    import numpy
    from itertools import product
    n, m, x, *ca = map(int, string.split())
    ca = numpy.array(ca).reshape((-1, m + 1)).T
    c, a = ca[0], ca[1:]
    ans = n * 10**5
    for b in product([0, 1], repeat=n):
        b = numpy.array(b)
        if (a @ b.T).min() >= x:
            ans = min(ans, c @ b.T)
    return str(ans if ans < n*10**5 else -1)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def min_needed_value(values, skills, X):
    cand = []
    for i in range(2**len(values)):
        get_skill = [0] * len(skills[0])
        get_value = 0
        for j in range(len(values)):
            if (i >> j) & 1:
                get_skill = [x + y for (x, y) in zip(get_skill, skills[j])]
                get_value += values[j]
        if all([s >= X for s in get_skill]):
            cand.append(get_value)
    sorted(cand)
    if len(cand) == 0: return -1
    else: return cand[0]


def main():
    N, M, X = map(int, input().split())
    values = []
    skills = []
    for _ in range(N):
        Book = list(map(int, input().split()))
        values.append(Book[0])
        skills.append(Book[1:])
    print(min_needed_value(values, skills, X))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def min_needed_value(values, skills, X):
    cand = []
    for i in range(2**len(values)):
        get_skill = [0] * len(skills[0])
        get_value = 0
        for j in range(len(values)):
            if (i >> j) & 1:
                get_skill = [x + y for (x, y) in zip(get_skill, skills[j])]
                get_value += values[j]
        if all([s > X for s in get_skill]): cand.append(get_value)
    sorted(cand)
    if len(cand) == 0: return -1
    else: return cand[0]


def main():
    N, M, X = map(int, input().split())
    values = []
    skills = []
    for _ in range(N):
        Book = list(map(int, input().split()))
        values.append(Book[0])
        skills.append(Book[1:])
    print(min_needed_value(values, skills, X))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, m, x = list(map(int, input().split()))
c = []
a = []

# c, aにデータを用意
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append([])
    
    for j in range(m):
        a[i].append(tmp[j])

money_min = -1
comb = []
# 組み合わせを用意
for l in range(n):
    tmp = combinations(range(n), l + 1)
    for i in tmp:
        comb.append(i)
    
# 組み合わせごとに考える
for el in comb:
    ables = []
    money = 0        
    scores = []

    # scoreに0をいれる
    for i in range(m):
        scores.append(0)

    # 組み合わせを足し合わせる
    for n in el:
        money += c[n] # 金
        for i in range(m):
            scores[i] += a[n][i] # 習得度

    # 判定
    for i in range(m):
        ables.append(scores[i] > x)

    # 良ければ金額更新
    if all(ables):
        money_min = money if money_min < 0 or money_min > money else money_min

print(money_min)

Submission status: Wrong Answer

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

# input
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):
    smart = [0] * M
    cost_sum = 0
    for i in range(N):
        if (S >> i) % 2 == 0:
            continue
        cost_sum += C[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: Wrong Answer

Solution code:
#bit全探索
n,m,x=map(int,input().split())
a=[]
for i in range(n):
    ai=list(map(int,input().split()))
    a.append(ai)

#可能判定
maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000
#全探索
for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)& 1):
            d.append(j)
    print(d)
    b=[0 for j in range(m)]
    #得た能力
    c=0
    #お金
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)

Submission status: Wrong Answer

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

prices = []
skills = []
if n > 0:
    patterns = 2 ** n
    ans = 10 ** 5 * n
    for i in range(patterns - 1, -1, -1):
        pattern = i
        skill = [0] * m
        price = 0
        for book in books:
            if pattern & 1 == 1:
                price += book[0]
                for j in range(1, m + 1):
                    skill[j-1] += book[j]
            pattern >>= 1
        prices.append(price)
        skills.append(skill)
        flg = True
        for k in skill:
            if k < x:
                flg = False
                break
        if flg:
            if ans > price:
                ans = price
    if ans == 10 ** 5 * n:
        ans = -1
else:
    ans = -1
print(str(ans))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, m, x = list(map(int, input().split()))
c = []
a = []

# c, aにデータを用意
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append([])
    
    for j in range(m):
        a[i].append(tmp[j])

money_min = -1
comb = []
# 組み合わせの数 1 - n
for l in range(n):
    # 組み合わせを用意
    tmp = combinations(range(n), l + 1)
    for i in tmp:
        comb.append(i)
    
# 組み合わせごとに考える
for el in comb:
    ables = []
    money = 0        
    scores = []

    # scoreに0をいれる
    for i in range(m):
        scores.append(0)

    # 組み合わせを足し合わせる
    for n in el:
        money += c[n] # 金
        for i in range(m):
            scores[i] += a[n][i] # 習得度

    # 判定
    for i in range(m):
        ables.append(scores[i] >= x)

    # 良ければ金額更新
    if all(ables):
        money_min = money if money_min < 0 or money_min > money else money_min

print(money_min)

Submission status: Wrong Answer

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

prices = [ ]
skills = [ ]
patterns = 2 ** n
ans = 10 ** 5 * n
for i in range(patterns - 1, -1, -1):
    pattern = i
    skill = [0] * m
    price = 0
    for book in books:
        if pattern & 1 == 1:
            price += book[0]
            for j in range(1, m + 1):
                skill[j-1] += book[j]
        pattern >>= 1
    prices.append(price)
    skills.append(skill)
    flg = True
    for k in skill:
        if k < x:
            flg = False
            break
    if flg:
        if ans > price:
            ans = price
if ans == 10 ** 5 * n:
    ans = -1
print(str(ans))

Submission status: Wrong Answer

Solution code:
#bit全探索
n,m,x=map(int,input().split())
a=[]
for i in range(n):
    ai=list(map(int,input().split()))
    a.append(ai)

maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000
#全探索
for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)and 1):
            d.append(j)
    b=[0 for j in range(m)]
    #得た能力
    c=0
    #お金
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)

Submission status: Wrong Answer

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

#全探索
for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)and 1):
            d.append(j)
    b=[0 for k in range(m)]
    #能力
    c=0
    #お金
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

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