AtCoder茶色解く３

今回解くのはこちら
C - Skill Up

本を購入するしないの２通りを全本の組み合わせに対して行うbit全探索であると推測、
進めていきます。

12冊の本を買ったか買っていないかでフラグ管理するとすると、
2^12=4^4=16^2=256通りで試せばいいことになります。

例えば以下のサンプルがある場合

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

n=5の場合、２進数で表すと101となります。
60 2 2 4と50 2 3 9が1となり採用され、残りの1行は採用されません。
それぞれの値は配列（aとする)に足しこまれます。

a=[60 2 2 4]+[50 2 3 9]=[110 4 5 13]となります。
その後、これらを比較し、a[1]~a[3]に対して必要スキルレベル以上かどうかを判定します。
今回は10に届かないので、この値は破棄します。

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

# 入力をすべて受け取る
for i in range(n):
  tmp = list(map(int, input().split()))
  inp.append(tmp)

# bit全探索を行うための箱づくり
sum = 0
min = 10**10
for i in range(2**n):
  tmp = [0]*m
  flg = 0
  
  # ある買う買わないのケースに対して、フラグが立ってたらスキルポイントを増やす
  for j in range(n):
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      sum += inp[j][0]
      for k in range(1,m+1):
        #print(n,j, k, tmp, inp)
        tmp[k-1] += inp[j][k]
  for ii, k in enumerate(tmp):
    if k < x: # x未満ならflgをたててNGとする
      flg = 1
      break
  #print(tmp, flg)
  if sum < min and flg == 0: min = sum
  sum = 0
  
if min == 10**10: min = -1
print(min)

bit全探索自体を作るのに時間がかかってしまったので、ほかの問題も解いてコツをつかみたい