Problem:


Score : 400 points

Problem Statement

One day, Niwango-kun, an employee of Dwango Co., Ltd., found an integer sequence (a_1, ..., a_N) of length N.
He is interested in properties of the sequence a.

For a nonempty contiguous subsequence a_l, ..., a_r (1 \leq l \leq r \leq N) of the sequence a, its beauty is defined as a_l + ... + a_r. Niwango-kun wants to know the maximum possible value of the bitwise AND of the beauties of K nonempty contiguous subsequences among all N(N+1)/2 nonempty contiguous subsequences. (Subsequences may share elements.)

Find the maximum possible value for him.

Constraints

2 \leq N \leq 1000

1 \leq a_i \leq 10^9

1 \leq K \leq N(N+1)/2

All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the answer.

Sample Input 1

4 2
2 5 2 5

Sample Output 1

12

There are 10 nonempty contiguous subsequences of a. Let us enumerate them:

contiguous subsequences starting from the first element: \{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}

contiguous subsequences starting from the second element: \{5\}, \{5, 2\}, \{5, 2, 5\}

contiguous subsequences starting from the third element: \{2\}, \{2, 5\}

contiguous subsequences starting from the fourth element: \{5\}

(Note that even if the elements of subsequences are equal, subsequences that have different starting indices are considered to be different.)

The maximum possible bitwise AND of the beauties of two different contiguous subsequences is 12.
This can be achieved by choosing \{5, 2, 5\} (with beauty 12) and \{2, 5, 2, 5\} (with beauty 14).

Sample Input 2

8 4
9 1 8 2 7 5 6 4

Sample Output 2

32



Sample input:
4 2
2 5 2 5


Sample output:
12

Submission status: Runtime Error

Solution code:
from itertools import *
from collections import *
from bisect import *


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

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=31
for i in range(len(nlst)):
    a=bin(nlst[i])[2:]
    nlst[i]=[0 for i in range(lenbin-len(a))]+list(map(int,list(a)))
    #print(nlst[i])
lenbinst=0

#print(nlst)
use=set([i for i in range(len(nlst))])
while lenbinst<lenbin:
    idx=-1
    count=0
    for m in use:
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        if len(nlst)!=lenbinst:
            for m in range(len(nlst)):
                if nlst[m][lenbinst]!=1:
                    uselst.remove(m)
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)

Submission status: Runtime Error

Solution code:
from itertools import *
from collections import *
from bisect import *


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

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=31
for i in range(len(nlst)):
    a=bin(nlst[i])[2:]
    nlst[i]=[0 for i in range(lenbin-len(a))]+list(map(int,list(a)))
    #print(nlst[i])
lenbinst=0

#print(nlst)
while lenbinst<lenbin:
    idx=-1
    count=0
    for m in range(len(nlst)):
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        if len(nlst)!=lenbinst:
            nlst=[i for i in nlst if i[idx]==1]
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)

Submission status: Runtime Error

Solution code:
from itertools import *
from collections import *
from bisect import *


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

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=31
for i in range(len(nlst)):
    a=bin(nlst[i])[2:]
    nlst[i]=[0 for i in range(lenbin-len(a))]+list(map(int,list(a)))
    #print(nlst[i])
lenbinst=0

#print(nlst)
while lenbinst<lenbin:
    idx=-1
    count=0
    for m in range(len(nlst)):
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        idx=lenbinst

    if idx==-1:
        pass
    else:
        nlst=[i for i in nlst if i[idx]==1]
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([0] + lr())
A_cum = A.cumsum()
beauties = []
for i, j in itertools.combinations(range(N+1), 2):
    beauties.append(A_cum[j] - A_cum[i])

beauties = np.array(beauties)
j = 0
def check(x):
    return np.sum(beauties&x == x) >= K

answer = 0
for i in range(40, -1, -1):
    if check(answer + 1 << i):
        answer += 1 << i

print(answer)
# 00

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array([0] + lr())
A_cum = A.cumsum()
beauties = []
for i, j in itertools.combinations(range(N+1), 2):
    beauties.append(A_cum[j] - A_cum[i])

beauties.sort(reverse=True)
j = 0
def check(x):
    return sum([x&y == x for y in beauties]) >= K

answer = 0
for i in range(40, -1, -1):
    if check(answer + 1 << i):
        answer += 1 << i

print(answer)
# 00

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
for i in range(len(lists)+1):
    for j in range(i,len(lists)):
        
        G=sum(lists[i:j+1])
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GH[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0

while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0


print(answer)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
SUM=[]
for i in range(K):
    SUM.append(sum(A[i:]))
ans=str(SUM.pop())
if SUM!=[]:
    for s in SUM:
        ans+='&'+(str(s))
print(eval(ans))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
SUM=[]
for i in range(K):
    SUM.append(sum(A[i:]))
if len(SUM)>1:
    ans=SUM[0]
    for i in range(1,K):
        ans=ans&SUM[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, K = [int(j) for j in input().split()]
a_list = [int(j) for j in input().split(' ')]

sub_arrays = []

for i in range(N):
    for j in range(i, N):
        sub_arrays.append(a_list[i:j+1])

utsukushisa_list = []
for sub in sub_arrays:
    utsukushisa_list.append(sum(sub))
print(utsukushisa_list)
utsuku_bin_list = [bin(j)[2:] for j in utsukushisa_list]

x = list(itertools.combinations(utsuku_bin_list, K))

max_result = 0

for islem in x:
    result = ''
    if islem[0] == islem[1]:
        continue
    for j in range(max(len(islem[0]), len(islem[1]))):
        if j < min(len(islem[0]), len(islem[1])):
            if islem[0][::-1][j] == '1' and islem[1][::-1][j] == '1':
                result += '1'
            else:
                result += '0'
        else:
            result += '0'
    result = result[::-1]
    result = int(result, 2)
    if result > max_result:
        max_result = result

print(max_result)

'''
1) alt kumelerini cikar
'''

Submission status: Runtime Error

Solution code:
N, K = [int(j) for j in input().split()]
a_list = [int(j) for j in input().split(' ')]

sub_arrays = []

import itertools # Kombinasyonlari bulmama yarayan kutuphane

for i in range(N):
    for j in range(i, N):
        sub_arrays.append(a_list[i:j+1])

utsukushisa_list = []
for sub in sub_arrays:
    utsukushisa_list.append(sum(sub))
print(utsukushisa_list)
utsuku_bin_list = [bin(j)[2:] for j in utsukushisa_list]

x = list(itertools.combinations(utsuku_bin_list, K))

max_result = 0

for islem in x:
    result = ''
    if islem[0] == islem[1]:
        continue
    for j in range(max(len(islem[0]), len(islem[1]))):
        if j < min(len(islem[0]), len(islem[1])):
            if islem[0][::-1][j] == '1' and islem[1][::-1][j] == '1':
                result += '1'
            else:
                result += '0'
        else:
            result += '0'
    result = result[::-1]
    result = int(result, 2)
    if result > max_result:
        max_result = result

print(max_result)

Submission status: Runtime Error

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
# import math
def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def main():
    n, k = getlist()
    nums = getlist()
    acc = [0]
    tmp = 0
    for num in nums:
        tmp += num
        acc.append(tmp)

    poss = []
    for r in range(n+1):
        for l in range(r):
            poss.append(acc[r] - acc[l])

    poss.sort()
    # print(poss)
    lborder, rborder = 0, (n * (n+1)) // 2

    ans, digit = 0, math.floor(math.log2(poss[-1])) + 1
    # print(digit)
    tmp = 0

    while(digit >= 0):
        tmp += 2 ** (digit - 1)
        mid = bisect.bisect_left(poss, tmp)
        if rborder - mid >= k:
            lborder = mid
        elif mid - lborder >= k:
            rborder = mid
            tmp -= 2 ** (digit - 1)
        else:
            print(tmp - 2 ** (digit - 1))
            return

        digit -= 1

    print(tmp)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    rui = [a[0]]
    for i in range(1, n):
        rui.append(rui[i - 1] + a[i])
    rui = [0] + rui
    ansl = []
    for i in range(n):
        for j in range(i,n):
            ansl.append(rui[j + 1] - rui[i])
    ansl = sorted(ansl, reverse=True)
    
    cnt = 0
    anscnt = 0
    ansbit = 0
    L = []
    for i in range(50):
        bit = (1 << (50 - i))
        l = []
        for j in range(len(ansl)):
            if ansl[j] & bit == 0:
                l.append(ansl[j])
            else:
                L.append(ansl[j])
                #ans &= ansl[j]
                cnt += 1
        if cnt >= k:
            ansbit = i
            break
        else:
            anscnt += len(L)
            for j in range(len(L)):
                ans &= L[j]
            L = []
        ansl = l

    ans = 0
    for i in range(ansbit,50):
        bit = (1 << (50 - i))
        LL = []
        cnt = 0
        for j in range(len(L)):
            if L[j] & bit == 0:
                l.append(L[j])
            else:
                cnt+=1
                #LL.append(L[j])

        if cnt >= k:
            #L = LL
            ans |= bit
                

    
    print(ans)
    
                    


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    rui = [a[0]]
    for i in range(1, n):
        rui.append(rui[i - 1] + a[i])
    rui = [0] + rui
    ansl = []
    for i in range(n):
        for j in range(i,n):
            ansl.append(rui[j + 1] - rui[i])
    ansl = sorted(ansl, reverse=True)
    
    cnt = 0
    anscnt = 0
    ansbit = 0
    L = []
    for i in range(50):
        bit = (1 << (50 - i))
        l = []
        for j in range(len(ansl)):
            if ansl[j] & bit == 0:
                l.append(ansl[j])
            else:
                L.append(ansl[j])
                #ans &= ansl[j]
                cnt += 1
        if cnt >= k:
            ansbit = i
            break
        else:
            anscnt += len(L)
            for j in range(len(L)):
                ans &= L[j]
            L = []
        ansl = l

    ans = 0
    for i in range(ansbit,50):
        bit = (1 << (50 - i))
        LL = []
        cnt = 0
        for j in range(len(L)):
            if L[j] & bit == 0:
                l.append(L[j])
            else:
                cnt+=1
                LL.append(L[j])

        if cnt >= k:
            L = LL
            ans |= bit
                

    
    print(ans)
    
                    


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import bisect
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
GYN=['Yes','trumpet']
mo=10**9+7
imp='IMPOSSIBLE'

n,k=MI()
a=LI()
A=[0]
for i in a:
    A+=[A[-1]+i]
b=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        b+=[A[j]-A[i]]
        
c=sorted(b)[-k:]
ans=0
i=0
i2=1
while i2<c[-1]*2:
    ans+=i2 if sum([j>>i&1 for j in c])==k else 0
    #print(i2,sum([j>>i&1 for j in c]))
    i2*=2
    i+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
Q = int(input())
for i in range(Q):
    a,b,c = map(int,input().split())
    if a*100+b*10+c % 2 == 1:
        print("No")
    else :
        x = a*100+10*b+c
        x /= 2
        while(x >= 100):
            x /= 100
        while(x >= 10):
            x /= 10
        while(x != 0):
            x -= 1
        if x == 0:
            print("Yes")