307133: CF1305G. Kuroni and Antihype
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Kuroni and Antihype
题意翻译
现在有n个人,并且给出他们的年龄。 两个人是朋友,当且仅当两个人年龄的按位与结果为0。 现在,有一个传销组织,每个人有两种操作: 1、主动加入传销组织,这样的话,传销组织不会给你钱; 2、邀请自己的一个朋友加入传销组织,这样的话,传销组织会奖励你数值等于你的年龄的钱。(当然,执行该操作的人必须已经进入传销组织了) 每个人只可以进入传销组织一次。 现在,请你输出,如果n个人通力合作,传销组织支付给这n个人的钱数之和最大是多少。 样例解释: 前两个人是朋友,让第二个人主动加入组织,并邀请第一个人加入,传销组织会奖励第二个人2块钱。 第三个人没有朋友,他主动加入传销组织,传销组织也不会给他钱。 所以,总共3个人可以获得2块钱。题目描述
Kuroni isn't good at economics. So he decided to found a new financial pyramid called Antihype. It has the following rules: 1. You can join the pyramid for free and get $ 0 $ coins. 2. If you are already a member of Antihype, you can invite your friend who is currently not a member of Antihype, and get a number of coins equal to your age (for each friend you invite). $ n $ people have heard about Antihype recently, the $ i $ -th person's age is $ a_i $ . Some of them are friends, but friendship is a weird thing now: the $ i $ -th person is a friend of the $ j $ -th person if and only if $ a_i \text{ AND } a_j = 0 $ , where $ \text{AND} $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Nobody among the $ n $ people is a member of Antihype at the moment. They want to cooperate to join and invite each other to Antihype in a way that maximizes their combined gainings. Could you help them?输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1\le n \le 2\cdot 10^5 $ ) — the number of people. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0\le a_i \le 2\cdot 10^5 $ ) — the ages of the people.
输出格式
Output exactly one integer — the maximum possible combined gainings of all $ n $ people.
输入输出样例
输入样例 #1
3
1 2 3
输出样例 #1
2