UOJ Logo Universal Online Judge

UOJ

#176. 新年的繁荣

统计

零点的钟声敲响,猴年终于到来啦~

在这新年的第一天,猴族首领猴腮雷打算重新规划一下猴族领地的交通。

猴族领地中有 $n$ 个城市,其中第 $i$ 座城市的繁荣度为 $a_i$。猴族领地中任意两个城市之间都可以修建双向道路,在第 $i$ 座城市和第 $j$ 座城市之间修建道路可以给新的一年带来 $a_i \mathbin{\mathrm{and}} a_j$ 的繁荣度。其中 $\mathbin{\mathrm{and}}$ 表示按位与运算,例如 $2 \mathbin{\mathrm{and}} 3=2$,$1 \mathbin{\mathrm{and}} 0=0$,$1 \mathbin{\mathrm{and}} 1=1$。

为了彰显自己的功绩,猴族首领猴腮雷决定修建若干条道路,使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达,为了发扬节约精神,他决定修建恰好 $n-1$ 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。

作为一个英明的首领,猴腮雷决定在所有可行的方案中选择繁荣度最大的方案,现在他想要知道他选择的方案的繁荣度,但是因为他日理万机,没有时间来想这种简单的小问题,于是他就让你来帮忙啦。

输入格式

第一行两个正整数 $n,m$。

接下来一行 $n$ 个非负整数表示 $a_i$ ,满足 $0 \leq a_i < 2^m$。

输出格式

输出所有方案中最大的繁荣度。

样例一

input

3 2
1 2 3

output

3

explanation

一个满足条件的方案是在城市 $\langle 1,3 \rangle, \langle 2,3 \rangle$ 之间修建道路。

样例二

input

4 3
1 2 4 7

output

7

explanation

一个满足条件的方案是在城市 $\langle 1,4 \rangle, \langle 2,4 \rangle, \langle 3,4 \rangle$ 之间修建道路。

样例三

见样例数据下载。

样例四

见样例数据下载。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $6$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 $n$ 的规模 $m$ 的规模
1$15$$n \leq 1000$$m \leq 18$
2$15$$n \leq 5000$
3$10$$n \leq 10^5$$m = 1$
4$15$$m \leq 12$
5$15$$m \leq 15$
6$30$$m \leq 18$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载