/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 から 2^N の番号がついた 2^N 人でじゃんけん大会を行います。
大会は以下の形式で行われます。
- 参加者を人 1、人 2、 \ldots、人 2^N の順に横一列に並べる。
- 現在の列の長さを 2M として、各 i\ (1\leq i \leq M) について左から 2i-1 番目の人と左から 2i 番目の人で試合を行い、負けた M 人を列から外す。これを N 回繰り返す。
ここで、人 i はちょうど j 回試合に勝つと C_{i,j} 円獲得できます。1 回も勝たなかった場合は何も貰えません。全ての試合の勝敗を自由に決められるとき、人 1、人 2、 \ldots、人 2^N が貰えるお金の合計の最大値を求めてください。
制約
- 1 \leq N \leq 16
- 1 \leq C_{i,j} \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{2^N,1} C_{2^N,2} \ldots C_{2^N,N}
出力
答えを出力せよ。
入力例 1
2 2 5 6 5 2 1 7 9
出力例 1
15
初めの列は (1,2,3,4) です。
人 1 と人 2 の試合で人 2 が勝ち、人 3 と人 4 の試合で人 4 が勝ったとすると、列は (2,4) になります。
次に人 2 と人 4 の試合で人 4 が勝ったとすると、列は (4) になり、これで大会が終了となります。
このとき、人 2 はちょうど 1 回勝ち、人 4 はちょうど 2 回勝ったので、貰えるお金の合計は 0+6+0+9=15 となります。 これが貰えるお金の合計の最大値です。
入力例 2
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 2
4
Score : 500 points
Problem Statement
2^N people, numbered 1 to 2^N, will participate in a rock-paper-scissors tournament.
The tournament proceeds as follows:
- The participants are arranged in a row in the order Person 1, Person 2, \ldots, Person 2^N from left to right.
- Let 2M be the current length of the row. For each i\ (1\leq i \leq M), the (2i-1)-th and (2i)-th persons from the left play a game against each other. Then, the M losers are removed from the row. This process is repeated N times.
Here, if Person i wins exactly j games, they receive C_{i,j} yen (Japanese currency). A person winning zero games receives nothing. Find the maximum possible total amount of money received by the 2^N people if the results of all games can be manipulated freely.
Constraints
- 1 \leq N \leq 16
- 1 \leq C_{i,j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{2^N,1} C_{2^N,2} \ldots C_{2^N,N}
Output
Print the answer.
Sample Input 1
2 2 5 6 5 2 1 7 9
Sample Output 1
15
The initial row of the people is (1,2,3,4).
If Person 2 wins the game against Person 1, and Person 4 wins the game against Person 3, the row becomes (2,4).
Then, if Person 4 wins the game against Person 2, the row becomes (4), and the tournament ends.
Here, Person 2 wins exactly 1 game, and Person 4 wins exactly 2 games, so they receive 0+6+0+9=15 yen in total, which is the maximum possible sum.
Sample Input 2
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 2
4