[R67E]活动1 - 代码源竞赛平台

时空限制

2S/512M

题目描述

某班级共有 $n$ 名同学，编号分别为 $0,1,\dots,n-1$。记所有同学组成的集合为 $S=\{0,1,\dots,n-1\}$。

老师准备组织一次小组活动，需要将所有同学分成若干个小组。不同的同学组合在一起时，可能会产生不同的合作效果。对于 $S$ 的任意非空子集 $T$，若这些同学被分到同一个小组中，则该小组的合作效果为 $a_T$。

现在，老师想把所有同学划分为 $k$ 个非空小组 $t_1,t_2,\dots,t_k$。为了保证活动中至少有一名同学能够独立完成一项任务，要求这些小组中至少存在一个只包含一名同学的小组，即存在 $1\le i\le k$，满足 $|t_i|=1$。

对于每个 $k=2,3,\dots,n$，你需要求出在所有满足条件的分组方案中，$\sum_{i=1}^k a_{t_i}$ 的最大值。

其中，$t_1,t_2,\dots,t_k$ 是 $S$ 的一个划分，当且仅当满足：

1. 每个 $t_i$ 都是非空集合；
2. 任意两组之间没有重复的同学；
3. 所有小组合起来正好包含全部同学。

格式

输入格式

第一行一个正整数 $n$。

第二行输入 $2^n-1$ 个整数，对于其中的第 $i$ 个整数（$1\le i < 2^n$），令 $X_i=\{j\mid j\in S,(i\ \&\ 2^j)=2^j\}$（其中 $\&$ 表示二进制按位与），则这个整数表示 $a_{X_i}$。

输出格式

输出 $n-1$ 行，其中第 $i$ 行输出一个整数表示 $k=i+1$ 时的答案。

样例

样例输入 #1

2
1 2 4

样例输出 #1

3

样例输入 #2

3
2 3 1 6 7 4 5

样例输出 #2

10
11

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$50$	$10$
$2$	$50$	$15$

对于 $100\%$ 的数据，满足 $2 \le n\le 15$，对于任意 $S$ 的非空子集 $T$，满足 $1\le a_T\le10^9$。