Problem:


Score : 500 points

Problem Statement

Seisu-ya, a store specializing in non-negative integers, sells N non-negative integers. The i-th integer is A_i and has a utility of B_i.
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.

Constraints

1 \leq N \leq 10^5

0 \leq K < 2^{30}

0 \leq A_i < 2^{30}(1\leq i\leq N)

1 \leq B_i \leq 10^9(1\leq i\leq N)

All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N K
A_1 B_1
:
A_N B_N

Outputs

Print the maximum possible sum of utilities of purchased integers.

Sample Input 1

3 5
3 3
4 4
2 5

Sample Output 1

8

Buy 2 and 3 to achieve the maximum possible total utility, 8.

Sample Input 2

3 6
3 3
4 4
2 5

Sample Output 2

9

Buy 2 and 4 to achieve the maximum possible total utility, 9.

Sample Input 3

7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9

Sample Output 3

32



Sample input:
3 5
3 3
4 4
2 5


Sample output:
8

Submission status: Accepted

Solution code:
import sys
from functools import reduce
# from math import log2 // New in Python 3.3, not in PyPy3 2.4 (Python 3.2.5)

N, K = map(int, input().split())

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = reduce(lambda v, ab: v + ab[1] if K | ab[0] == K else v, AB, 0)
# for i in range(int(log2(K)), 0, -1):
for i in range(int.bit_length(K) - 1, 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = reduce(lambda v, ab: v + ab[1] if km | ab[0] == km else v, AB, 0)
    ans = max(ans, anscand)
print(ans)

Submission status: Accepted

Solution code:
import sys
# from math import log2 // New in Python 3.3, not in PyPy3 2.4 (Python 3.2.5)

N, K = map(int, input().split())

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = sum([b for a, b in AB if K | a == K])
# for i in range(int(log2(K)), 0, -1):
for i in range(int.bit_length(K) - 1, 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = sum([b for a, b in AB if km | a == km])
    ans = max(ans, anscand)
print(ans)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = 0
kbin = bin(K)[2:]
for a, b in AB:
    if K | a == K:
        ans += b
for i in range(1, len(kbin)):
    if kbin[i - 1] == "0":
        continue
    kl = list(kbin)
    kl[i - 1] = "0"
    for j in range(i, len(kbin)):
        kl[j] = "1"
    km = int("".join(kl), 2)
    anscand = 0
    for a, b in AB:
        if km | a == km:
            anscand += b
    if ans < anscand:
        ans = anscand
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
ad=dict()
al=ad.keys()
for i in range(N):
    a,b=map(int,input().split())
    if not a in ad:
        ad[a]=b
    else:
        ad[a]+=b

bk=bin(K)
lbk=len(bk)-2
k1=2**(lbk-1)-1
kl=[]
for i in range(lbk):
    ki=str(bk)[i+2]
    if ki=='1':
        kk=2**(lbk-1-int(i))
        kl.append((K-kk)|(kk-1))
kl.append(K)
kll=[0for i in range(len(kl))]
for i in range(len(kl)):

    for n in al:
        if n | kl[i]==kl[i]:
            kll[i]+=ad[n]
print(max(kll))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
L = K.bit_length()

koho = [K]
tmp = 0
for b in reversed(range(L)):
	if (K>>b) & 1:
		tmp += (1<<b)
		koho.append(tmp-1)

nums = [0]*len(koho)
for _ in range(N):
	A,B = inpl()
	for i,k in enumerate(koho):
		if k|A == k:
			nums[i] += B

print(max(nums))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=[tuple(map(int,input().split())) for _ in range(n)]
b=bin(k)[2:]
r=sum(b for a,b in s if k|a==k)
for i in range(len(b)-1):
    if b[i]=='0':
        continue
    l=int(b[:i]+'0'+'1'*(len(b)-i-1),2)
    r=max(r,sum(b for a,b in s if l|a==l))
print(r)

Submission status: Accepted

Solution code:
N, K = map(int,raw_input().split())
dict={K:0}
count = 0
k=bin(K)[2:]
a="111111111111111111111111111111" 
for i in k:
    if i == "1":
        dict[int(k[:count]+"0"+a[count+1:len(k)],2)] = 0
    count += 1
 
for i in range(0,N):
    a , b = map(int,raw_input().split())
    for j in dict:
        if j | a == j:
            dict[j] += b
        else:
            pass
        continue
M = 0
for i in dict:
    M = max(M,dict[i])
print M

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

l = []

kb = bin(k)
ll = [k]

for i in range(len(kb) - 2):
    if kb[i + 2] == '1':
        ll.append(int(kb[:i + 2] + '0' + '1' * (len(kb) - (i + 3)), 2))

for i in ll:
    ans = 0
    for j in range(n):
        if i == ab[j][0] | i:
            ans += ab[j][1]
        l.append(ans)

print(max(l))

Submission status: Accepted

Solution code:
def solve(K, ABs):
    if not ABs: return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
    for p in pool:
        v = 1 << p
        KK = (K >> p) << p
        KKK = (K >> p)
        t = sum(b for a, b in ABs if (not(a & v) and ((a | KK) >> p) == KKK))
        if t > ansK:
            ansK = t
    return ansK
   

N, K = map(int, input().split())
ABs = []
for i in range(N):
    a, b = map(int, input().split())
    if a > K: continue
    ABs.append([a, b])

print(solve(K, ABs))

Submission status: Accepted

Solution code:
def solve(K, ABs):
    if not ABs: return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
    for p in pool:
        v = 1 << p
        KK = (K >> p) << p
        KKK = (K >> p)
        t = sum(b for a, b in ABs if (not(a & v) and (a | KK) >> p == KKK))
        if t > ansK: ansK = t
    return ansK
   

N, K = map(int, input().split())
ABs = []
for i in range(N):
    a, b = map(int, input().split())
    if a > K: continue
    ABs.append([a, b])

print(solve(K, ABs))

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().strip().split()]
ls = []
for _ in range(n):
    ls.append(tuple(int(x) for x in input().strip().split()))

bk = bin(k)[2:]
cands = [k]
for i in range(len(bk)):
    if bk[i] == '1':
        cands.append(int(bk[:i] + '0' + '1'*(len(bk)-i-1), base=2))

m_ = len(cands)
max_ = [0] * m_

for a, b in ls:
    for i in range(m_):
        if a | cands[i] == cands[i]:
            max_[i] += b

print(max(max_))

Submission status: Runtime Error

Solution code:
import sys
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1
    ans=0
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            ans=max(ans,sum([e[1] for e in ab if e[0]|m==m]))
    ans=max(ans,sum([e[1] for e in ab if e[0]|k==k]))
    print(max(cand))

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
data = []
bit_k = format(k, 'b')
len_k = len(bit_k)
for i in range(n):
    a, b = map(int, input().split())
    if a <= k:
        tmp = format(a, 'b')
        tmp = tmp.zfill(len_k)
        data.append([tmp,b])
def check_value(bit):
    res = 0
    for i in range(len(data)):
        flag = True
        dd = data[i][0]
        for j in range(len_k):
            if bit[j] == '0' and dd[j] == '1':
                flag = False
                break
        if flag:
            #print("tmp:{} bit{}".format(tmp, bit))
            res += data[i][1]
    return res
ans = 0
tmp = []
for i in range(len_k):
    p = []
    if bit_k[i] == '1':
        p = tmp + ['0'] + ['1']*(len_k-1-i)
    else:
        continue
    p = "".join(p)
    ans = max(ans, check_value(p))
    tmp += bit_k[i]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from copy import deepcopy
from math import log
N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
#n=int(ceil(log(K,2)))+1
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
ans=sum([b for a,b in AB if K|a==K])
print(bin(K))
for i in range(int.bit_length(K)-1,0,-1):
    if not K &(1<<i):
        continue
    m=K & ~(1<<i)|(1<<i)-1
    print(bin(m))
    s=sum([b for a,b in AB if m | a ==m])
    ans=max(s,ans)
print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log
N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
n=int(ceil(log(K,2)))+1
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
        n=max(n,int(ceil(log(a,2)))+1)
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(n)
    AB_.append([k,i[1]])
AB=AB_
k=bin(K)[2:].zfill(n)
l=len(AB)
Klist=[k]
for i in range(n):
    if k[i]=="1":
        if i+1>=len(k)-1:
            Klist.append(k[:i]+"0")
            continue
        Klist.append(k[:i]+"0"+"1"*len(k[i+1:]))
#print(Klist)
ans=0
for i in Klist:
    sum=0
    for j,h in AB:
        if int(i,2)|int(j,2)<=int(i,2):
            #print(i,j,int(i,2)|int(j,2),int(i,2))
            sum+=h
    ans=max(sum,ans)
print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil

from collections import defaultdict
from math import log
N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
n=int(ceil(log(K,2)))+1
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
        n=max(n,int(ceil(log(a,2)))+1)
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(n)
    AB_.append([k,i[1]])
AB=AB_
k=bin(K)[2:].zfill(n)
l=len(AB)
Klist=[k]
for i in range(n):
    if k[i]=="1":
        Klist.append(k[:i]+"0"+"1"*len(k[i+1:]))
#print(Klist)
ans=0
for i in Klist:
    sum=0
    for j,h in AB:
        if int(i,2)|int(j,2)<=int(i,2):
            #print(i,j,int(i,2)|int(j,2),int(i,2))
            sum+=h
    ans=max(sum,ans)
print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log
N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
n=int(ceil(log(K,2)))+1
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
        n=max(n,int(ceil(log(a,2)))+1)
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(n)
    AB_.append([k,i[1]])
AB=AB_
k=bin(K)[2:].zfill(n)
l=len(AB)
dp=[[0]*(n+1) for i in range(l)]
for i in range(l):
    for j in range(n):
        #print(i,j,dp[i][j]<<1,"j:",k[j],"k:",AB[i][0][j])
        dp[i][j+1]=(dp[i][j]<<1)+int(k[j])|int(AB[i][0][j])
        #print((dp[i][j]<<1)+int(k[j])|int(AB[i][0][j]))
ans=0
for i in range(n):
    if k[i]=="1":
        sum=0
        for j in range(l):
            if AB[j][0][i]=="0" and dp[j][i]<=int(k[:i],2):
                sum+=AB[j][1]
        ans=max(ans,sum)
sum=0
t=k
for j in range(l):
    if int(t)|int(AB[j][0])<=int(t):
        sum+=AB[j][1]
ans=max(ans,sum)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(4)
    AB_.append([k,i[1]])
AB=AB_
l=len(AB)

k=bin(K)[2:].zfill(4)
ans=0
for i in range(4):
    if k[i]=="1":
        t=k[:i]+"0"
        sum=0
        for j in range(l):
            if int(t)|int(AB[j][0][:i+1])<=int(t):
                sum+=AB[j][1]
        ans=max(ans,sum)
sum=0
t=k
for j in range(l):
    if int(t)|int(AB[j][0])<=int(t):
        sum+=AB[j][1]
ans=max(ans,sum)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import log2

N, K = map(int, input().split())

AB = []
for _ in range(N):
    AB.append([int(s) for s in input().split()])

ans = sum([b for a, b in AB if K | a == K])
for i in range(int(log2(K) // 1), 0, -1):
    if not K & (1 << i):
        continue
    km = K & ~(1 << i) | (1 << i) - 1
    anscand = sum([b for a, b in AB if km | a == km])
    ans = max(ans, anscand)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(N)]
def max_(A,n):
    B=[0]*(n+1)
    for [w,p] in A:
        for j in range(n,w-1,-1):
            if B[j-w]+p>B[j]:
                B[j]=B[j-w]+p
    return max(B)
print(max_(A,K))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
masks = [K]

bs = str(bin(K))[2:]
for i in range(len(bs) - 1):
    if bs[i] == '1':
        a = len(bs) - 1 - i
        mask = K - (1 << a)
        mask |= ((1 << a) - 1)
        masks.append(mask)

anss = [0 for i in range(K)]
for i in range(N):
    a,b = map(int,input().split())
    for i,m in enumerate(masks):
        if (m | a) == m:
            anss[i] += b

print(max(anss))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
k = format(K, '031b')
n = k.find("1")
ans = 0

for i in range(N):
    judge = 0
    a, b = map(int, input().split())
    a = format(a, '031b')
    for j in range(n+1, 31):
        if (k[j] == 0) and (a[j] == 1):
            judge = 1
            break
        if (k[j] == 1) and (a[j] == 0):
            break
    if judge == 0:
        ans += b

ans2 = 0

for i in range(N):
    judge = 0
    a, b = map(int, input().split())
    a = format(a, '031b')
    if a[n] == 0:
        ans2 += b


print(min(ans, ans2))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python                                                                                          
#-*- coding: utf-8 -*-                                                                                         

if __name__ == "__main__":
    N, K = map(int, raw_input().split())
    A = []
    B = []
    C = []
    for n in range(N):
        input =	map(int, raw_input().split())
        A.append(input[0])
        B.append(input[1])
        C.append(input[1] / float(input[0]))
    ans = 0
    while min(A) < K:
        max_index = C.index(max(C))
        ans += A[max_index]
        A = A[0:max_index] + A[max_index+1:len(A)]
	B = B[0:max_index] + B[max_index+1:len(B)]
        C = C[0:max_index] + C[max_index+1:len(C)]
    print ans

Submission status: Runtime Error

Solution code:
def solve(K, ABs):
    if not ABs: return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
    for p in pool:
        v = 1 << p
        KK = (K >> p) << p
        KKK = (K >> p)
        t = sum(b for a, b in ABs if (not(a & v) and (a | KK) >> p == KKK)
        if t > ansK: ansK = t
    return ansK
   

N, K = map(int, input().split())
ABs = []
for i in range(N):
    a, b = map(int, input().split())
    if a > K: continue
    ABs.append([a, b])

print(solve(K, ABs))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

l = []
a = 0

for i in range(30):
    if k > 2 ** i:
        a = i

for i in range(2 ** a, k):
    ans = 0
    for j in range(n):
        if i == ab[j][0] | i:
            ans += ab[j][1]
        l.append(ans)

print(max(l))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
N,K=map(int,input().rstrip().split())

lst=[]

for i in range(N):
    A,B=map(int,input().rstrip().split())
    C=B/A
    tpl=(A,B,C)
    lst.append(tpl)

lst.sort( key=lambda x:x[1], reverse=True )
lst.sort( key=lambda x:x[2], reverse=True )

# for j in lst:
#     print(j)

maxKey=0
maxVal=0
for j in lst:
    tmpKey=maxKey+j[0]
    if( K < tmpKey ):
        continue
    maxKey+=j[0]
    maxVal+=j[1]

print(maxVal,flush=True)

Submission status: Runtime Error

Solution code:
res=0
for d in range(K):
    tmp_res=0
    for key in data.keys():
        if(key|d==d):
            tmp_res+=data[key]
    #print(d,tmp_res)
    if(tmp_res>res):
        res=tmp_res
print(res)

Submission status: Runtime Error

Solution code:
def solve(K, ABs):
    if not ABs return 0
    ansK = sum(b for a, b in ABs if (K | a) == K)
    pool = []
    for i in range(30, -1, -1):
        if (K & (1<<i)):
            pool.append(i)
        else:
            if pool:
                break
    for p in pool:
        v = 1 << p
        t = sum(b for a, b in ABs if not(a & v))
        if t > ansK: ansK = t
    return ansK
   

N, K = map(int, input().split())
ABs = []
for i in range(N):
    a, b = map(int, input().split())
    if a > K: continue
    ABs.append([a, b])

print(solve(K, ABs))

Submission status: Runtime Error

Solution code:
from math import log2
n,k = map(int,input().split())
loglen = 2**int(log2(k))
pud = 2**(int(log2(k - loglen))) - 1 + loglen
pud2 = loglen-1

ansk = 0
ansp = 0
ans2 = 0
for _ in range(n):
    a,b = map(int,input().split())
    if a|k == k: ansk += b
    if a|pud == pud: ansp += b
    if a|pud2 == pud2: ans2 += b

print(max(ansk,ansp,ans2))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
from collections import deque

N,K=map(int,input().rstrip().split())

lst=[]

for i in range(N):
    A,B=map(int,input().rstrip().split())
    C=B/A
    tpl=(A,B,C)
    lst.append(tpl)

lst.sort( key=lambda x:x[1], reverse=True )
lst.sort( key=lambda x:x[2], reverse=True )

for j in lst:
    print(j)

maxKey=0
maxVal=0
for j in lst:
    tmpKey=maxKey+j[0]
    if( K < tmpKey ):
        continue
    maxKey+=j[0]
    maxVal+=j[1]

print(maxVal,flush=True)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100001)

def dp(a,k):
    if a==N:
        return 0

    if k in t[a]:
        return t[a][k]

    kk = k|A[a]
    if kk > K:
        ret = dp(a+1,k)
    else:
        ret = max(dp(a+1,k), dp(a+1,kk)+B[a])
    t[a][k] = ret
    return ret

N, K = map(int, input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
t = [{} for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int, input().split())


print(dp(0,0))

Submission status: Runtime Error

Solution code:
def dp(a,k):
    if a==N:
        return 0

    if k in t[a]:
        return t[a][k]

    kk = k|A[a]
    if kk > K:
        ret = dp(a+1,k)
    else:
        ret = max(dp(a+1,k), dp(a+1,kk)+B[a])
    t[a][k] = ret
    return ret

N, K = map(int, input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
t = [{} for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int, input().split())


print(dp(0,0))

Submission status: Runtime Error

Solution code:
def dp(a,k):
    if a==N:
        return 0

    kk = k|A[a]
    if kk > K:
        return dp(a+1,k)
    else:
        return max(dp(a+1,k), dp(a+1,kk)+B[a])

N, K = map(int, input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int, input().split())


print(dp(0,0))