問題概要
問題ページ
-
-
C - Skill Up
問題ページへ移動する
問題文
競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが \(M\) 個あります。
最初、各アルゴリズムの理解度は \(0\) です。
高橋くんが書店に行くと、\(N\) 冊の参考書が売っていました。\(i\) 番目の参考書 (\(1\leq i\leq N\)) は \(C_i\) 円で売られていて、購入して読むことで、各 \(j\) (\(1\leq j\leq M\)) について \(j\) 番目のアルゴリズムの理解度が \(A_{i,j}\) 上がります。
また、それ以外の方法で理解度を上げることはできません。
高橋くんの目標は \(M\) 個すべてのアルゴリズムの理解度を \(X\) 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。
制約
- 入力はすべて整数
- \(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\)
問題の考察
ACコード
import sys
import itertools
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, m, x = list(map(int, input().rstrip('\n').split()))
ls = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
m_cost = 10 ** 20
for it_v in itertools.product([True, False], repeat=n):
cost = 0
score = [0] * m
for i in range(n):
if it_v[i]:
cost += ls[i][0]
for j in range(1, m + 1):
score[j - 1] += ls[i][j]
is_ok = True
for i in range(m):
if score[i] < x:
is_ok = False
break
if is_ok:
m_cost = min(m_cost, cost)
print(m_cost if m_cost != 10 ** 20 else -1)
if __name__ == '__main__':
solve()