Tenka1 Programmer Contest D - IntegerotS

Problem Statement

Seisu-ya, a store specializing in non-negative integers, sells N non-negative integers. The i-th integer is Ai and has a utility of Bi. There may be multiple equal integers with different utilities.

Takahashi will buy some integers in this store. He can buy a combination of integers whose bitwise OR is less than or equal to K. He wants the sum of utilities of purchased integers to be as large as possible.

Find the maximum possible sum of utilities of purchased integers.

解题报告：

这题从物品下手不好做，可以考虑从k下手，所以我们枚举最后的答案，一定是小于等于k的，所以直接枚举比k小的集合，这样的集合是很多的，但很多可以归为一类，我们这样归类：首先一个小于等于k的数一定是前面部分和k相同或更小，然后某一位k是1，而答案是0，所以枚举这一位作为分类的依据，只要是答案子集的都计入贡献，取Max即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=100005;

int n,m;

struct node{

	int x,y;

}a[N];

ll ans=0;

void work()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	ll tot=0,li=0;m++;

	for(int i=30;i>=0;i--){

		if(m&(1<<i)){

			li^=(1<<i);tot=0;

			for(int j=1;j<=n;j++)

				if((a[j].x&li)==0)tot+=a[j].y;

		   ans=Max(tot,ans);

			li^=(1<<i);

		}

		else li^=(1<<i);

	}

	printf("%lld\n",ans);

}

int main()

{

	work();

	return 0;

}