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: Runtime Error

Solution code:
def read_stdin():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    return (n, k, p)


def main(n, k, p):
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]

    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size - 1):
        # if mask[i] == '1':
        rest = bit_size - i - 1
        k_alt = int(mask[:i] + '0' + ('1' * (bit_size - i - 1) if rest > 0 else ''), 2)
        score = 0
        for j in range(n):
            if k_alt | p[j][0] == k_alt:
                score += p[j][1]
        max_score = max(max_score, score)
    print(max_score)


if __name__ == '__main__':
    n, k, p = read_stdin()
    main(n, k, p)

Submission status: Runtime Error

Solution code:
def read_stdin():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    return (n, k, p)

def main(n, k, p):
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]

    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size - 1):
        if mask[i] == '1':
            rest = bit_size - i - 1
            k_alt = int(mask[:i] + '0' +
                        ('1' * (bit_size - i - 1) if rest > 0 else ''), 2)
            score = 0
            for j in range(n):
                if k_alt | p[j][0] == k_alt:
                    score += p[j][1]
            max_score = max(max_score, score)
    print(max_score)

if __name__ == '__main__':
    n,k,p = read_stdin()
    main(n, k, p)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]
    
    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size-1):
        if mask[i] == '1':
            rest = bit_size-i-1
            k_alt = int(mask[:i] + '0' + ('1' * (bit_size-i-1) if rest>0 else ''), 2)
            score = 0
            for j in range(n):
                if k_alt | p[j][0] == k_alt:
                    score += p[j][1]
            max_score = max(max_score, score)
    print(max_score)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]
    
    mask = bin(k)[2:]
    bit_size = len(mask)
    for i in range(bit_size-1):
        if mask[i] == '1':
            k_alt = int(mask[:i] + '0' + '1' * (bit_size-i-1), 2)
            score = 0
            for j in range(n):
                if k_alt | p[j][0] == k_alt:
                    score += p[j][1]
            max_score = max(max_score, score)
    print(max_score)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    p = []
    for i in range(n):
        a, b = map(int, input().split())
        if a <= k:
            p.append((a, b))
    max_score = 0
    for i in range(n):
        if k | p[i][0] == k:
            max_score += p[i][1]
    
    mask = bin(k)[2:]
    for i in range(len(mask)):
        if mask[i] == '1':
            k_alt = int(mask[:i] + '0' + '1' * len(mask[i+1:]), 2)
            score = 0
            for j in range(n):
                if k_alt | p[j][0] == k_alt:
                    score += p[j][1]
            max_score = max(max_score, score)
    print(max_score)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, raw_input().split(' '))
kbin = bin(K)[2:]
klen = len(kbin)

vs = [0]*30
vs2 = [0]*30
for n in xrange(N):
  a, b = map(int, raw_input().split(' '))
  abin = bin(a)[2:]
  alen = len(abin)
  vs[-alen-1] += b
  if a <= (K % (2**alen)):
    vs2[-alen] += b

ans = [0]*30
tmp = 0
for i in xrange(-klen, 0):
  ans[i] += vs[i] + tmp
  tmp += vs2[i]

print max(ans)

Submission status: Runtime Error

Solution code:
n, k = list(map(int, input().split()))
a = []
b = []
for _ in range(n):
    cur_a, cur_b = list(map(int, input().split()))
    a.append(cur_a)
    b.append(cur_b)

memo = {}

def rec(i, j):
    if (i, j) in memo.keys():
        return memo[(i, j)]
    if i == n:
        res = 0
    elif k < a[i] | j:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, a[i]|j)+b[i])
    memo[(i, j)] = res
    return res

print(rec(0, 0))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [tuple(int(x) for x in input().split()) for _ in range(N)]
A = [(a, b) for a, b in A if a <= K]
# print(A)
L = K.bit_length()
ans = 0
for i in reversed(range(L)):
    bit = (1 << i) & K
    if bit != 1:
        # print(bit, ':', i)
        cand = 0
        bor = 0
        for a, b in A:
            if ((a >> i) & 1) == 0:
                # print(a, (a >> i) & 1)
                cand += b
                bor ^= a
        ans = max(ans, cand)
        assert(bor <= K)
print(ans)

Submission status: Runtime Error

Solution code:


N , K =  list(map(int,input().split()))
keta = 0
for i in range(1000):
    if 2**i > K:
       keta=i
       break

K_2 = bin(K)[2:]

max_kouho = [K_2,"1"* (len(K_2) -1) ]

for i in range(1,len(K_2)-1):
    if K_2[i] == "1" :
        #print(K_2[:i-1]+"00"+ ("1" * 100)[- (len(K_2)-i-1 if len(K_2)-i-1 > 0 else 100 ):] )
        max_kouho.append(
            (K_2[:i]+"0"+ ("1" * 100) )[:len(K_2)] )
#print(max_kouho)


AB  = [ list(map(int,input().split())) for _ in range(N)]
#ans =0

dp = {key:0 for key in max_kouho}
ans_use_top = 0     # 100111
ans_not_use_top = 0 # 011111
for a,b in AB:
    #use
    for key in max_kouho:
        if int(key,2) |a ==int(key,2):
            dp[key]+=b
    #print(bin(a),b,dp)

print(max(dp[key] for key in max_kouho ))