Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21792. 【NOIP Round #6】抉择

统计

题目描述

给定一个长度为 $n$ 的非负整数序列 $[a_1,\dots,a_n]$,求它的一个子序列 $[a_{i_1},a_{i_2},\dots,a_{i_k}]\ (1\le i_1\lt i_2\lt \dots\lt i_k\le n)$,使得 $\sum_{j=1}^{k-1}(a_{i_j}\operatorname{and} a_{i_{j+1}})$ 最大。你只需要输出这个最大值即可。

这里,$\operatorname{and}$ 是指二进制按位与。

子序列的定义是:从原序列中任意删除若干个(可以是 0 个)数,将剩下的数按原来的相对顺序拼起来,得到的序列。

输入格式

第一行一个正整数 $n$。接下来一行 $n$ 个整数 $a_1\sim a_n$。

输出格式

输出一个整数,为 $\sum_{j=1}^{k-1}(a_{i_j}\operatorname{and} a_{i_{j+1}})$ 的最大值。

样例

样例输入 1

5
1 2 3 1 3

样例输出 1

5

样例 1 解释

一种最优解为:取子序列为 $[a_2,a_3,a_5]$。

样例输入 2

2
1000000000000 987654321234

样例输出 2

965637836800

样例 3,4

见下发文件。

数据范围

所有数据均满足:$1\le n\le 10^{6}$,$0\le a_i\le 10^{12}$。

  • 子任务 1($20$ 分):$n\le 20$。
  • 子任务 2($25$ 分):$n\le 5000$。
  • 子任务 3($20$ 分):$n\le 10^5,a_i\lt 512$。
  • 子任务 4($15$ 分):$n\le 2\times 10^5$,每个 $a_i$ 都是在 $[0,10^{12}]$ 独立均匀随机生成的。
  • 子任务 5($20$ 分):无特殊限制。