E - Product Development

Contest Duration: 2023-09-30(Sat) 12:00 - 2023-09-30(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Product Development Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $475$ 点

問題文

AtCoder 社はある商品の開発をしようとしています。この商品には $K$ 個のパラメーターがあり、現段階ではすべてのパラメーターの値が $0$ です。AtCoder 社の目標は、パラメーターの値を全て $P$ 以上にすることです。

ここで、 $N$ 個の開発案があります。 $i(1 \le i \le N)$ 個目の開発案を実行すると、 $1 \le j \le K$ を満たす整数 $j$ 全てに対して $j$ 個目のパラメーターが $A_{i,j}$ 上がりますが、この開発案を実行するにはコストが $C_i$ かかります。

同じ開発案を $2$ 回以上実行することは出来ません。AtCoder 社が目標を達成出来るか判定し、出来る場合は目標を達成するのに必要なコストの総和の最小値を求めてください。

制約

$1 \le N \le 100$
$1 \le K,P \le 5$
$0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)$
$1 \le C_i \le 10^9(1 \le i \le N)$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$   $P$ 
 $C_1$   $A_{1,1}$   $A_{1,2}$   $\dots$   $A_{1,K}$ 
 $C_2$   $A_{2,1}$   $A_{2,2}$   $\dots$   $A_{2,K}$ 
 $\dots$ 
 $C_N$   $A_{N,1}$   $A_{N,2}$   $\dots$   $A_{N,K}$

出力

AtCoder 社が目標を達成出来るならば目標を達成するのに必要なコストの総和の最小値を、出来ないならば -1 を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$1$ 個目と $3$ 個目と $4$ 個目の開発案を実行すると、それぞれのパラメーターが $3+2+0=5,0+4+1=5,2+0+4=6$ で全て $5$ 以上となるため目標を達成できます。この場合コストの総和は $5 + 3 + 1 = 9$ となります。

コストの総和 $8$ 以下で目標を達成することは出来ません。よって答えは $9$ です。

入力例 2Copy

Copy

出力例 2Copy

Copy

-1

どのようにしても目標を達成することは出来ません。よって -1 を出力します。

Score : $475$ points

Problem Statement

AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$ .

There are $N$ development plans. Executing the $i$ -th development plan ( $1 \le i \le N$ ) increases the value of the $j$ -th parameter by $A_{i,j}$ for every integer $j$ such that $1 \le j \le K$ , at the cost of $C_i$ .

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

$1 \le N \le 100$
$1 \le K,P \le 5$
$0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)$
$1 \le C_i \le 10^9(1 \le i \le N)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $K$   $P$ 
 $C_1$   $A_{1,1}$   $A_{1,2}$   $\dots$   $A_{1,K}$ 
 $C_2$   $A_{2,1}$   $A_{2,2}$   $\dots$   $A_{2,K}$ 
 $\dots$ 
 $C_N$   $A_{N,1}$   $A_{N,2}$   $\dots$   $A_{N,K}$

Output

If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

If you execute the first, third, and fourth development plans, each parameter will be $3+2+0=5,0+4+1=5,2+0+4=6$ , all of which are at least $5$ , so the goal is achieved. The total cost in this case is $5 + 3 + 1 = 9$ .

It is impossible to achieve the goal at a total cost of $8$ or less. Thus, the answer is $9$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

-1

You cannot achieve the goal no matter what you do. Thus, print -1.