ビットDP 練習問題 4 C++編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
この問題は、前回の「ビットDP 練習問題 3」と N の制約のみが異なります。
より高速な解法を考えて解いてみましょう。
ヒントを掲示します。
前回の問題では dp 配列を dp[i][s] と二次元配列で定義していましたが、これを dp[s] と一次元配列で定義してみましょう。
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 ≦ 19
・ 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
-
17
215193437 512280586 313871509 715195693 236056216 307457594 356393389 246928340 39495607 400989924 85655402 126941050 166969811 640698804 910625503 394717462 12027784
315071741 638465550 919446822 36817454 868725684 78258693 415700224 55214113 528157217 73412414 122115761 431647925 53297966 90031723 859919800 186322262 985670041
718004868 260476522 306186399 352966645 769913710 315672436 971739961 360426357 750235178 139788770 47133630 142744878 573021221 422221663 921471143 195755127 462707108
547503094 333265875 831200107 276740833 735676094 788262497 795018557 411648642 731770657 701461280 180842613 274410587 177022053 627008530 321405293 763092139 68475984
111258059 248496435 472325112 268640255 297511310 267731936 883463958 134070831 856234404 394818596 242582537 675697333 812005495 729988037 593969769 570571145 279388559
167007259 579384948 548761334 431322503 99718037 280784829 517488158 568118531 523833468 853400760 682730300 946406217 156919356 384975516 240274568 999624830 89219444
683607348 441352135 487828875 429296166 410848108 930029813 358102784 134428618 514445939 298817058 716839502 273914213 976427291 377620044 896003109 506367770 948014672
12371033 726727343 164877548 804030731 617817867 574915044 318783623 424238540 340824131 860561079 36214978 468193677 865799959 767674621 48718662 533910478 546051544
604240085 986187583 192436914 196826870 595037330 338103430 271471124 890764302 986171653 301151949 776750552 55227747 298314790 367975125 50013136 906454196 265984173
227034785 399488667 237807955 86751703 350809659 785750860 73903292 5416362 787910047 642330116 730227320 24816362 954719556 826538897 513331236 544280781 126775443
800126357 611152980 69142964 107037030 564080952 193168001 960474503 616560839 625840203 196820071 65608759 26410505 685945017 895011501 15554318 980173374 856694915
675433986 923756800 154141408 906392927 231883211 986807093 408331187 743439206 990243494 316738760 314593833 741752021 896244043 754514872 914810263 832781448 467942722
104355358 523132726 909806902 321909117 102009016 808600924 127599052 336251403 448189892 451382920 595168685 556591126 887386239 969026355 195292605 578946215 279127281
920945797 347573044 946533620 634895260 550460347 289926492 528013026 217582278 122503943 30294686 974046104 799757560 805209573 517147520 417185560 995001462 926191127
702580533 832701989 854632398 414783496 184877507 408028924 468194249 965759951 958508014 501284901 578299995 769658289 661934612 501752943 599751839 37754035 873326977
480086218 379427845 198951327 822021658 73958518 732351316 773131525 830988348 39062848 745970910 432819330 268808449 191755009 905607880 627706768 304133841 510635919
75431530 328148761 263873595 956755600 546672553 19225341 471541998 606799431 910468333 814903592 896894845 270836039 164860564 738050466 367102270 98353268 342025523
- 出力例3
-
15676043839
