Submission #1773762

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long tot = 0;
		int v = 0;
		for(int i=0;i<N;i++){
			tot += B[i];
			v |= A[i];
		}
		
		if(v <= K){
			Console.WriteLine(tot);
			return;
		}
		
		long min = long.MaxValue;
		bool[] del = new bool[N];
		for(int j=30;j>=0;j--){
			int kj = (K >> j) & 1;
			int vj = (v >> j) & 1;
			
//Console.WriteLine("j:{0},kj:{1},vj:{2}",j,kj,vj);
			if(kj == 0 && vj == 0) continue;
			if(kj == 1 && vj == 0){
				//ここまでひきわけにできていれば ここで決着がつく．
				long t = 0;
				for(int i=0;i<N;i++) if(del[i]) t += B[i];
				min = Math.Min(min, t);
			}
			if(kj == 1 && vj == 1){
				//ここまで引き分けにしてきた分プラス今回分で決着をつけられる
				long t = 0;
				for(int i=0;i<N;i++) if(del[i] || ((A[i] >> j) & 1) == 1) t += B[i];
				min = Math.Min(min, t);
			}
			if(kj == 0 && vj == 1){
				//ここは引き分けにして下位で決着をつける
				for(int i=0;i<N;i++) if(((A[i] >> j) & 1) == 1) del[i] = true;
			}
		}
		
		// 完全に引き分けにできた場合もOK
		long t0 = 0;
		for(int i=0;i<N;i++) if(del[i]) t0 += B[i];
		min = Math.Min(min, t0);
		
		Console.WriteLine(tot - min);
		
	}
	int N,K;
	int[] A;
	long[] B;
	public Sol(){
		var d = ria();
		N = d[0]; K = d[1];
		A = new int[N];
		B = new long[N];
		for(int i=0;i<N;i++){
			d = ria();
			A[i] = d[0];
			B[i] = d[1];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

Submission Info

Judge Result