ビットDP 練習問題 Java編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 工場ではロボットの制作をしており、工場にはロボットのパーツが N 個あります。
各パーツには「強さ」「軽さ」「かっこよさ」 の 3 つの評価点があります。
i 個目のパーツの強さは A_{i,1} 点、軽さは A_{i,2} 点、かっこよさは A_{i,3} 点です。
いまから K 個のパーツを選んでロボットを作ります。
この工場で制作するロボットには基準点があり、強さ P_1 点以上、軽さ P_2 点以上、かっこよさ P_3 点以上のパーツがそれぞれ 1 つ以上必要です (すべての基準点を 1 つのパーツが満たす必要はないことに注意してください)。
より形式的には、選ぶパーツの集合を S としたとき、以下の条件を満たす必要があります。
・すべての k (1 ≦ k ≦ 3) について、P_k ≦ A_{j,k} を満たす j (j ∈ S) が 1 つ以上存在する
条件を満たすようにパーツを選んだとき、選んだパーツの各評価点の総和 ΣΣ A_{j,k} (j ∈ S, 1 ≦ k ≦ 3) の最大値を出力してください。
ただし、条件を満たすパーツの選び方が存在しない場合は -1 を出力してください。
入力例 1 を説明します。
2 個目のパーツと 4 個目のパーツを選んだ場合、条件を満たしており、選んだパーツの各評価点の総和は (10 + 23 + 2) + (0 + 0 + 6) = 41 です。
条件を満たして各評価点の総和を 42 以上にすることはできないので、41 を出力します。
入力例 2 では、どのようにしても条件を満たすようにパーツを選ぶことはできません。
入力例 3 のように、答えが 32 bit 整数に収まらない場合があることに注意してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N K
P_1 P_2 P_3
A_{1,1} A_{1,2} A_{i,3}
A_{2,1} A_{2,2} A_{2,3}
...
A_{N,1} A_{N,2} A_{N,3}
・ 1 行目には、ロボットのパーツの数を表す整数 N が与えられます。
・ 続く N 行には、パーツの強さ A_{i,1}、軽さ A_{i,2}、かっこよさ A_{i,3} が与えられます。
・ 入力は合計で N+2 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
条件を満たすようにパーツを選んだとき、選んだパーツの各評価点の総和 ΣΣ A_{j,k} (j ∈ S, 1 ≦ k ≦ 3) の最大値を出力してください。
ただし、条件を満たすパーツの選び方が存在しない場合は-1を出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ K < N ≦ 1000
・ 0 ≦ P_k ≦ 10^9
・ 0 ≦ A_{j,k} ≦ 10^9
- 入力例1
-
4 2
8 9 6
10 23 2
7 8 5
0 0 6
100 1 4
- 出力例1
-
41
- 入力例2
-
5 3
269170747 975459373 705464275
151197289 141984783 450194987
164649930 976469494 278397414
223758104 364264976 972658137
129623539 998502723 796896735
21465050 998069787 155162900
- 出力例2
-
-1
- 入力例3
-
10 6
796730543 21171930 93935602
763957858 581238346 528312816
71621545 777588286 809319532
836783749 843098619 29778951
579526544 791472164 641002141
112179760 794391876 179273497
822432151 117313578 781433194
774056272 854924528 413257088
860608631 3692834 205567396
487103941 7717179 248213129
324816062 857007262 14147400
- 出力例3
-
11017117362
