ビットDP 練習問題 3 R(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 大学には N 人の男性と N 人の女性の合計 2N 人の生徒がいます。
paiza 大学では、男と女のそれぞれに番号が振られており、男 i (1 ≦ i ≦ N)、女 j (1 ≦ j ≦ N) と番号で呼ばれています。
いまから N 組の男女ペアを作ります。
どの男も誰か 1 人の女とペアにならなければならず、どの女も誰か 1 人の男とペアにならなければなりません。
男 i と女 j がペアになるとき、そのペアの相性を A_{i,j} とします。
できたペアの相性の総和の最大値を求めてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_{1,1} A_{1,2} ... A_{1,N}
A_{2,1} A_{2,2} ... A_{2,N}
...
A_{N,1} A_{N,2} ... A_{N,N}
・ 1 行目には、整数 N が与えられます。
・ 続く N 行には、男女の相性を表す整数 A_{i,j} が与えられます。
・ 入力は合計で 1 + N 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
できたペアの相性の総和の最大値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 16
・ 0 ≦ A_{i,j} ≦ 10^9
- 入力例1
-
3
1 2 3
2 5 4
6 3 1
- 出力例1
-
14
- 入力例2
-
4
2 3 4 1
5 3 2 3
3 2 3 3
2 1 0 3
- 出力例2
-
14
- 入力例3
-
10
698966129 287483764 920654297 987062196 560964201 627414070 627409373 624113972 724439422 526035396
842784733 137350730 841472711 819169152 780211906 784246731 349914497 594002545 664728117 920122460
293577893 307601853 600838145 716538239 463908203 808729508 499615686 580820825 911813385 87620249
308070865 555651918 107526518 622688727 139586463 475745315 175970018 466655767 176293982 48748984
578572221 394131882 817508948 259712662 142141951 247410682 154481449 578401971 167644182 272198315
612778115 645703646 138428708 898847185 480531762 421131139 596656988 379681047 654974622 546763177
822275454 78706649 714611089 151410236 196263826 541763972 397323510 947693607 189104953 26357827
527881351 926022956 420706308 562854190 996810529 168211924 855797718 817481158 693296341 760617535
738039081 146651858 636680528 11068608 346948491 577576382 636440380 191830378 728701267 761898312
669064169 947044788 358282514 358407521 902055348 534388790 204208409 142967869 278360457 938327662
- 出力例3
-
8338497297
