Score : $500$ points

问题描述

$2^N$ 名编号为 $1$ 到 $2^N$ 的人将参加一场剪刀石头布锦标赛。

比赛过程如下：

• 参赛者按照从左到右的顺序排列成一行，依次为参赛者 $1$、参赛者 $2$、$\ldots$、参赛者 $2^N$。
• 设当前行的长度为 $2M$。对于每个 $i\ (1\leq i \leq M)$，从左边数第 $(2i-1)$ 位和第 $(2i)$ 位参赛者进行一场比赛。然后，从行中移除这 $M$ 名输家。这个过程重复 $N$ 次。

其中，如果参赛者 $i$ 赢得了恰好 $j$ 场比赛，他们将获得 $C_{i,j}$ 日元（日本货币）。赢得零场比赛的人不会得到任何奖励。在所有比赛结果都可以自由操纵的情况下，找出这 $2^N$ 名参赛者可以获得的最大总金额。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:08:16