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: Accepted

Solution code:
n,kk= map(int, input().split())
a= list(map(int, input().split()))
x=[]
for i in range(n):
    v=0
    for j in range(i,n):
        v+=a[j]
        x.append(v)
x.sort()
r=len(bin(x[-1]))-2

ans=0
flag=False
# 高い位からbitが立つか調べる
v=[]
for i in range(r-1,-1,-1):
    cnt=0
    v.append(i)
    for j in x:
        flag=True
        for k in v:
            if not (j>>k)&1:
                flag=False
                break
        if flag:
            cnt+=1

    if cnt>=kk:
        ans+=pow(2,i)
    else:
        v.pop(-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k, *a = map(int, read().split())
now = []
ans = 0
for i, aa in enumerate(a):
    v = aa
    now.append(v)
    for aaa in a[i + 1:]:
        v += aaa
        now.append(v)
for m in range(40, -1, -1):
    ans *= 2
    cnt = 0
    bit = 1 << m
    nxt = []
    for num in now:
        if num & bit:
            cnt += 1
            nxt.append(num)
    if k <= cnt:
        ans += 1
        now = nxt
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
subs=[]
for i in range(n):
    s=0
    for j in reversed(range(i+1)):
        s+=a[j]
        subs.append(s)
keta=0
smax=10**12
while smax>0:
    smax//=2
    keta+=1
#print(subs)
ans=0
for i in reversed(range(keta+1)):
    lis=[]
    for num in subs:
        if (num>>i)&1:
            lis.append(num)
    if len(lis)>=k:
        ans+=pow(2,i)
        subs=lis
    else:
        if len(subs)==len(lis):
            ans+=pow(2,i)
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])
	# print(B)
	S = []
	for i in range(N + 1):
		for j in range(i + 1, N + 1):
			S.append(B[j] - B[i])
	# print(S)

	z = 0
	for i in range(41):
		z += 2 ** (40 - i)
		cnt = 0
		for j in S:
			if z & j == z:
				cnt += 1
		if cnt < K:
			z -= 2 ** (40 - i)

	print(z)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
a = LIST()

l = []

for i in range(1, N+1):
	tmp = sum(a[:i])
	for j in range(N-i+1):
		l.append(tmp)
		tmp -= a[j]
		if j+i <= N-1:
			tmp += a[j+i]

ans = 0
for i in range(max(l).bit_length()-1, -1, -1):
	nextl = []
	for x in l:
		if (x>>i)&1:
			nextl.append(x)
	if len(nextl) >= K:
		ans += 1<<i
		l = nextl
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
l=[]
ans=[]
for i in range(N):
    buf=0
    for j in range(i,N):
        buf=buf+a[j]
        l.append(buf)
#print(l)
for i in range(40,-1,-1):
    piv=[]
    for j in range(len(l)):
        if (l[j]>>i)&1:
            piv.append(l[j])
    if len(piv)>=K:
        l=piv
        ans.append(i)
    #print(piv,l)
cnt=0
for i in ans:
    cnt=cnt+pow(2,i)
print(cnt)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,K = LI()
A = LI()

sa = list(itertools.accumulate([0]+A))
b = []
for i in range(N):
    for j in range(i+1,N+1):
        b.append(sa[j]-sa[i])
#b.sort(reverse=True)
max_b = max(b).bit_length()

mask = 0
for i in range(max_b-1,-1,-1):
    bit = 2**i
    cnt = 0
    for x in b:
        if x & mask == mask:
            cnt += (x & bit > 0)
    if cnt >= K:
        mask += bit
print (mask)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,K = LI()
A = LI()

sa = list(itertools.accumulate([0]+A))
b = []
for i in range(N):
    for j in range(i+1,N+1):
        b.append(sa[j]-sa[i])
b.sort(reverse=True)
max_b = (max(b)).bit_length()

mask = 0
for i in range(max_b-1,-1,-1):
    bit = 2**i
    cnt = 0
    for x in b:
        if x & mask == mask:
            cnt += (x & bit > 0)
    if cnt >= K:
        mask += bit

print (mask)

Submission status: Accepted

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

# 全要素を列挙する　O(N^2) = 10 ** 6 (1000 * 999 // 2)
beauty = []
for i in range(N):
  cur = 0
  for j in range(i, N):
    cur += A[j]
    beauty.append(cur)

keta = len(bin(max(beauty))[2:])

for i in range(len(beauty)):
  beauty[i] = bin(beauty[i])[2:].zfill(keta)
  
# 入力例1の全要素
# 0010
# 0111
# 1001
# 1110
# 0101
# 0111
# 1100
# 0010
# 0111
# 0101
# ある桁のビットに1がK個以上あれば、その桁は1にできる
# 最大値が大きいほど良いので、頭の桁から貪欲に候補を選んでいけばよい。

ans = 0
for k in range(keta):
  # 0桁目から順に見る
  # その桁でK個以上の"1"を得ることができるのであれば、全て候補となる。
  # その桁が0のデータは候補からすべて除外してよい。
  # 同時に、その桁の美しさを答えに加算する (2 ** (keta - k - 1))
  # その桁にK個以上の"1"が存在しない場合は候補を絞る必要がないので何もしない10
  # 計算量は、要素数が10**6、桁数がlog(10 ** 9 * 10 ** 3) = 40
  # なので10 ** 7未満
  temp = []
  cnt = 0
  for j in range(len(beauty)):
    if beauty[j][k] == "1":
      temp += [beauty[j]]
      cnt += 1
  if cnt >= K:
    beauty = temp
    ans += 2 ** (keta - k - 1)

print(ans)

Submission status: Accepted

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

S = []
for l in range(0, N):
  temp = 0
  for r in range(l, N):
    temp += A[r]
    S.append(temp)

max_s = max(S)
n = max_s.bit_length()
S_temp = [S, []]
s_idx = 0
for i in range(n-1, -1, -1):
  c = 0
  for s in S_temp[s_idx]:
    if (s >> i) & 1:
      S_temp[s_idx-1].append(s)
      c += 1
  if c == K:
    ans = S_temp[s_idx-1][0]
    for _s in S_temp[s_idx-1]:
      ans &= _s
    print(ans)
    quit()
  if c > K:
    S_temp[s_idx] = []
    s_idx = not s_idx
  else:
    S_temp[s_idx-1] = []

ans = S_temp[s_idx][0]
for _s in S_temp[s_idx][:K]:
  ans &= _s

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

n,k = map(int, input().split())
a = list(map(int, input().split()))
keta = len(bin(sum(a)))-3
sumlist = []
cumsum = [0]+list(accumulate(a))
for key,v1 in enumerate(cumsum):
  for v2 in cumsum[key+1:]:
    sumlist.append(v2-v1)
ans = 0
for i in range(keta,-1,-1):
  tmp = []
  for j in sumlist:
    if (j >> i) & 1:
      tmp.append(j)
  if len(tmp) >= k:
    ans += 2 ** i
    sumlist = tmp
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 12
import sys
sys.setrecursionlimit(1000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    subarray = []
    for i in range(n):
        subarray.append(a[i])
        sub = a[i]
        for j in range(i - 1,-1,-1):
            sub += a[j]
            subarray.append(sub)
    
    for bit in range(50,-1,-1):
        next = []
        for sub in subarray:
            if (sub>>bit)&1:
                next.append(sub)
        if len(next) >= k:
            subarray = next
    
    ans = subarray[0]
    for i in range(1,len(subarray)):
        ans &= subarray[i]
    print(ans)   
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
# from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
rlst=ruiseki(a)
# print(rlst)
lst=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        # print(i,j)
        lst.append(rlst[j]-rlst[i])
# print(lst)
tmp=math.log(rlst[-1],2)
now=int(tmp)

while now>=0:
    anslst=[]
    for i in range(len(lst)):
        if 1&(lst[i]>>now)==1:
            anslst.append(lst[i])
    if len(anslst)>=k:
        lst=anslst
    now-=1
# print(lst)
ans=lst[0]
for i in range(k):
    ans=ans&lst[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
# from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
# def input():
#     return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
rlst=ruiseki(a)
# print(rlst)
lst=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        # print(i,j)
        lst.append(rlst[j]-rlst[i])
# print(lst)
tmp=math.log(rlst[-1],2)
now=int(tmp)

while now>=0:
    anslst=[]
    for i in range(len(lst)):
        if 1&(lst[i]>>now)==1:
            anslst.append(lst[i])
    if len(anslst)>=k:
        lst=anslst
    now-=1
# print(lst)
ans=lst[0]
for i in range(k):
    ans=ans&lst[i]
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
P = [0]+A
for i in range(1,n+1):
    P[i] += P[i-1]
temp = []
for i in range(n+1):
    for j in range(i+1, n+1):
        temp.append(P[j]-P[i])
ans = 0
for i in range(40, -1, -1):
    cur = ans+2**i
    cnt = 0
    for j in range(len(temp)):
        if temp[j]&cur == cur:
            cnt += 1
        if cnt >= k:
            break
    if cnt == k:
        ans += 2**i
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import copy

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

A=[0]+list(accumulate(A))
data=[]
for i in range(0,N):
    for j in range(i+1,N+1):
        data.append(A[j]-A[i])

digit=40
q=copy.copy(data)
ans=0
while digit>=0:
    test=[[] for i in range(0,digit+1)]
    for i in range(0,len(q)):
        for j in range(0,digit+1):
            if q[i]>>j & 1==1:
                test[j].append(q[i])

    for i in range(0,digit+1):
        if len(test[digit-i])>=K:
            ans+=2**(digit-i)
            q=copy.copy(test[digit-i])
            digit=digit-i-1
            break
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

A_acc = [0]+list(accumulate(A))
cand = []

for l in range(N):
    for r in range(l+1, N+1):
        cand.append(A_acc[r]-A_acc[l])
cand = sorted(cand)
ans = 0
for i in reversed(range(41)):
    k_candidates = []
    for c in cand:
        if c & (1 << i):
            k_candidates.append(c)
    if len(k_candidates) >= K:
        ans += 1 << i
        cand = k_candidates
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,k=[int(j) for j in input().split()]
a=np.array([int(j) for j in input().split()])
aa=a.cumsum()
l=aa[:,None]-aa[None,:]+a[None,:]
l=l.flatten()
l=l[l>0]

def f(x):
    return np.sum(l&x==x)>=k

left=0
right=1<<40
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
cums = [0]
for a in A:
    cums.append(cums[-1] + a)
vs = []
for l in range(n):
    for r in range(l+1, n+1):
        vs.append(cums[r] - cums[l])
vs.sort(reverse=True)


for i in range(100, -1, -1):
    tmp = []
    for v in vs:
        if v&(1<<i):
            tmp.append(v)
    if len(tmp) >= k:
        vs = tmp

if len(vs)<k:
    print(0)
else:
    ans = vs[0]
    for v in vs[1:]:
        ans &= v
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
candidates = []
for i, _ in enumerate(A):
    add_num = 0
    for a in A[i:]:
        add_num += a
        candidates.append(add_num)

ans = 0
for i in range(40, -1, -1):
    k_candidates = []
    for candidate in candidates:
        if candidate & (1 << i):
            k_candidates.append(candidate)
    if len(k_candidates) >= K:
        ans += 1 << i
        candidates = k_candidates
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
a = list(map(int,input().split()))
S = [0]*N
S[0] = a[0]
for k in range(1,N):
    S[k] = S[k-1] + a[k]
S = [0] + S
T = []
for k in range(N):
    for l in range(k+1,N+1):
        T.append(S[l]-S[k])
ans = 0
for d in range(41,-1,-1):
    c = 0
    for e in T:
        if (ans+2**d)&e == ans+2**d:
            c += 1
    if c >= K:
        ans += 2**d
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))

B = []
for i in range(n):
    B.append(A[i])
    s = A[i]
    for j in range(i+1, n):
        s += A[j]
        B.append(s)
        
res = 0
for i in range(42):
    p = res + 2**(41-i)
    cnt = 0
    for b in B:
        if p == p&b:
            cnt += 1
    if cnt >= k:
        res = p
print(res)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0] +list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i] 
nums = []
for i in range(n):
    for j in range(i+1,n+1):
        nums.append(a[j]-a[i])
nums.sort(reverse = True)
def count(x,lis):
    res = 0
    for i in range(len(lis)):
        if (lis[i]&x) == x:res+=1
    return res
def ok(x,lis):
    if count(x,lis) >=k:return True
    else:return False
ans = 0
for i in range(40,-1,-1):
    if ok(ans|1<<i,nums):ans|=1<<i

print(ans)

Submission status: Accepted

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

S = []
for i in range(N):
    s = 0
    for a in A[i:]:
        s += a
        S.append(s)

def isOk(n):
    return sum([n & a == n for a in S]) >= K

ans = 0
for d in range(40)[:: -1]:
    if isOk(ans | (1 << d)):
        ans |= (1 << d)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
sal = [0] * (n*(n+1)//2)
l = 0
for i in range(n):
  for j in range(i,n):
    sal[l] = sum(a[i:j+1])
    l += 1
ans = 0
for i in range(41)[::-1]:
    cnt = 0
    temp = ans + 2**i
    for j in sal:
        if temp&j == temp:
            cnt += 1
    if cnt >= k:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    from itertools import accumulate
    acc = list(accumulate([0] + A))
    S = []
    for i in range(N):
        for j in range(i+1, N+1):
            S.append(acc[j] - acc[i])
    S.sort(reverse=True)
    ans = 0
    for t in range(41, -1, -1):
        cur = 0
        for i in range(N*(N+1)//2):
            if ans + 2**t & S[i] == ans + 2**t:
                cur += 1
            if K == cur:
                break
        if K <= cur:
            ans += 2**t
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
for i,a in enumerate(A):
    k = 0
    for c in A[i:]:
        k += c
        B.append(k)

ans = 0
for i in range(40,-1,-1):
    C = []
    for b in B:
        if b&(1<<i):
            C.append(b)
    if len(C) >= K:
        B = C
        ans += 2**i
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = [int(item) for item in input().split()]
cuma = [0]
for item in a:
    cuma.append(cuma[-1] + item)
b = []
for i in range(n):
    for j in range(i + 1, n+1):
        b.append(cuma[j] - cuma[i])
ans = 0
for i in range(41, -1, -1):
    subset = []
    for item in b:
        if item & 1 << i: 
            subset.append(item)
    if len(subset) >= k:
        ans |= 1 << i
        b = subset[:]
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, K = map(int, input().split())
A = list(map(int, input().split()))

partial = []
for i in range(N):
    tmp = list()
    for j in range(i, N):
        tmp.append(A[j])
        partial.append(sum(tmp))


ret = 0
p = 1
x = 0
for i in range(50, -1, -1):
    p = pow(2, i)
    k = 0
    for a in partial:
        if (p+x) & a == (p+x):
            k += 1
    if k >= K:
        ret += p
        x += p

print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def search(i, L, Lnum, K):
    if i > 40: return 0
    add = pow(2, 40 - i)
    nextK = []
    count = 0
    for l in L:
        if l & add == add:
            nextK.append(l)
            count += 1
    #print(i, L)
    if count >= K: return add + search(i+1, nextK, count, K)
    else: return search(i+1, L, Lnum, K)


def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    sumA = [0] * (N + 1)
    for i, a in enumerate(A): sumA[i+1] = sumA[i] + a
    subA = []
 
    for i in range(N):
        for j in range(i+1, N+1): subA.append(sumA[j] - sumA[i])

    print(search(0, subA, N * (N + 1) // 2, K))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())
ls = []
n = 0
for i in range(N):
  m = A[i]
  ls.append(m)
  n = max(n,m)
  for j in range(i+1,N):
    m += A[j]
    ls.append(m)
    n = max(n,m)
s = bin(n)[2:]
L = len(s)
ans = 0
for i in range(L):
  x = L-i
  cnt = 0
  pre = []
  for l in ls:
    if l.bit_length()<x:
      continue
    j = l.bit_length()-x
    if bin(l)[2:][j]=='1':
      cnt += 1
      pre.append(l)
  if cnt>=K:
    ls = pre
    ans += 2**(x-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
A = LI()
acc = [0] + list(accumulate(A))
L = []
for i in range(n):
    for j in range(i + 1, n + 1):
        L += [acc[j] - acc[i]]

ans = 0
for l in range(max(L).bit_length() - 1, -1, -1):
    new_L = []
    for e in L:
        if e >> l & 1:
            new_L += [e]
    if len(new_L) >= k:
        ans |= 1 << l
        L = new_L

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = []
a = list(map(int,input().split()))
for i in range(len(a)):
  c = 0
  for j in range(len(a)-i):
    c += a[i+j]
    l.append(c)
m = len(bin(sum(a)))-2
x = 0
for i in range(m-1,-1,-1):
  c = 0
  cu = 2**i
  for j in l:
    if x+cu & j == x+cu:
      c += 1
    if c == k:
      x += cu
      break
print(x)

Submission status: Accepted

Solution code:
import copy
import bisect
import math

def bit_and(s, ans):
    if s[-1] == 0:  return ans

    n = int(math.log2(s[-1]))
    ind = bisect.bisect_left(s, 2**n)
    if len(s) - ind == K:
        temp = s[-1]
        for i in range(1, K):
            temp &= s[-i-1]
        return ans + temp
    elif len(s) - ind > K:
        ans += 2**n
        return bit_and(sorted([x & (2**n-1) for x in s[ind:]]), ans)
    else:
        return bit_and(sorted([x & (2**n-1) for x in s]), ans)


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

s = [a[0]]
for i in range(1, N):
    s.append(s[i-1] + a[i])
ps = copy.copy(s)
for i in range(N):
    ps = [ps[j] - ps[0] for j in range(1, N-i)]
    s += ps

print(bit_and(sorted(s), 0))

Submission status: Accepted

Solution code:
import copy
import bisect
import math

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

s = [a[0]]
for i in range(1, N):
    s.append(s[i-1] + a[i])
ps = copy.copy(s)
for i in range(N):
    ps = [ps[j] - ps[0] for j in range(1, N-i)]
    s += ps

ans = 0
s.sort()

while s[-1] != 0:
    n = int(math.log2(s[-1]))
    ind = bisect.bisect_left(s, 2**n)
    if len(s) - ind == K:
        temp = s[-1]
        for i in range(1, K):
            temp &= s[-i-1]
        print(ans + temp)
        exit()
    elif len(s) - ind > K:
        ans += 2**n
        s = [x & (2**n-1) for x in s[ind:]]
    else:
        s = [x & (2**n-1) for x in s]
    s.sort()
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, k = LI()
    a = LI()
    acc = [0] + list(itertools.accumulate(a))
    lis = []
    for i in range(n):
        for j in range(i + 1, n + 1):
            lis.append(acc[j] - acc[i])
    lis.sort()
    ans = deque()
    for l in lis:
        ans.append(l)
    ansnum = 0
    N = len(bin(acc[-1])) - 2
    for i in range(N):
        tmp = deque()
        lenans = len(ans)
        for _ in range(lenans):
            p = ans.popleft()
            if (1 << (N - 1 - i)) & p:
                ans.append(p)
            else:
                tmp.append(p)
        if len(ans) < k:
            while tmp:
                t = tmp.pop()
                ans.append(t)
        else:
            ansnum |= (1 << (N - 1 - i))
    print(ansnum)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
a = list(map(int, input().split()))
acc = [0] + list(accumulate(a))
ss = []
for r in range(N):
    for l in range(r+1):
        ss.append(acc[r+1] - acc[l])
ans = 0
idx = list(range(len(ss)))
for i in range(40)[::-1]:
    nidx = []
    for j in idx:
        if ss[j] >> i & 1 == 1:
            nidx.append(j)
    if len(nidx) >= K:
        ans += 1 << i
        idx = nidx
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)

Acum = A.cumsum()

Apair = np.subtract.outer(Acum, Acum) + A
Apair = np.tril(Apair).ravel()
Apair = Apair[Apair > 0]

d = 45  # 10*9*1000 = 1<<40ぐらい
ans = 0
while d >= 0:
    Atmp = np.bitwise_and(np.right_shift(Apair, d), 1)
    if np.count_nonzero(Atmp) >= K:
        ans += 2 ** d
        Apair = Apair[np.nonzero(Atmp)]
    d -= 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
Acum = [0]
for a in A:
    Acum.append(Acum[-1] + a)

Apair = []
for i, al in enumerate(Acum):
    for ar in Acum[i + 1:]:
        Apair.append(ar - al)
Apair = np.asarray(Apair, dtype=np.int64)

d = 45  # 10*9*1000 = 1<<40ぐらい
ans = 0
while d >= 0:
    Atmp = np.bitwise_and(np.right_shift(Apair, d), 1)
    if np.count_nonzero(Atmp) >= K:
        ans += 2 ** d
        Apair = Apair[np.nonzero(Atmp)]
    d -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, combinations
import numpy as np

read = sys.stdin.read

N, K, *a = map(int, read().split())

a = accumulate([0] + a)
seq = []
for i, j in combinations(a, 2):
    seq.append(j - i)

seq = np.array(seq, np.int64)
m = (10 ** 9 * 1000).bit_length()
answer = 0
bit = 1 << (m - 1)
for _ in range(m):
    tmp = seq[seq & bit == bit]
    if np.count_nonzero(tmp) >= K:
        answer += bit
        seq = tmp
    bit >>= 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, combinations

read = sys.stdin.read

N, K, *a = map(int, read().split())

a = accumulate([0] + a)
seq = []
for i, j in combinations(a, 2):
    seq.append(j - i)

m = (10 ** 9 * 1000).bit_length()
answer = 0
bit = 1 << (m - 1)
for _ in range(m):
    tmp = [i for i in seq if i & bit == bit]
    if len(tmp) >= K:
        answer += bit
        seq = tmp
    bit >>= 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, combinations

read = sys.stdin.read

N, K, *a = map(int, read().split())

a = accumulate([0] + a)
seq = []
for i, j in combinations(a, 2):
    seq.append(j - i)

m = (10 ** 9 * 1000).bit_length()
answer = 0
bit = 1 << (m - 1)
for _ in range(m):
    tmp = bit + answer
    if len([i for i in seq if i & tmp == tmp]) >= K:
        answer = tmp
    bit >>= 1

print(answer)

Submission status: Accepted

Solution code:
"""
第5回 ドワンゴからの挑戦状 予選  B - Sum AND Subarrays

考えたこと
N <= 1000なので、部分列の美しさは全列挙できる
美しさをK個選んで来た時のそれらの論理積　→　bitごとに計算すればOK

K個選ぶ場合の数が多いので間に合わない　→　全体についてどのbitが立っているか見ていってK以上個立ってるbitから上位K個をえらんだらいけるか？
・「K以上個立ってるbitから上位K個をえらんだら」　←ちゃんと選んだ美しさについて論理積とる。残ったりするbitがあるかもなので
"""


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

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

B = []
for l in range(N):
    for r in range(l,N):
        if l == 0:
            B.append(cm[r])
        else:
            B.append(cm[r] - cm[l-1])

# 2**40 = 1.0~~ * 10**12
stack = B
nxt_stack = []
for i in range(41,-1,-1):
    cnt = 0
    nxt_stack = []
    for b in stack:
        if b & (1 << i):
            cnt += 1
            nxt_stack.append(b)

    # 採用するbitの立っていない物は捨てる    
    if cnt >= K:
        stack = nxt_stack


ans = 0
if len(stack) >= K:
    for i in range(K):
        if i == 0:
            ans = stack[0]
        else:
            ans &= stack[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))
S = [0]
for i in range(n):
    S.append(A[i] + S[-1])
B = []
for i in range(len(S)):
    for j in range(i+1, len(S)):
        B.append(S[j] - S[i])
# B.sort()
# print(B)

ans = 0
for i in range(50, -1, -1):
    ans += 2**i
    c = 0
    for j in range(len(B)):
        if B[j] & ans == ans:
            c += 1
    # print(i, c)
    if c < k:
        ans -= 2**i
print(ans)

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    _a = list(map(int,input().split()))
    l = sum(_a).bit_length()
    cum = [0]
    for i in range(N):
        cum.append(cum[-1]+_a[i])

    a = []
    for i in range(1,N+1):
        for j in range(i):
            a.append(cum[i]-cum[j])

    bit = 2**(l-1)
    use = []
    ans = 0
    for _ in range(l):
        for num in a:
            if num&bit == bit:
                use.append(num)
        if len(use) >= K:
            ans += bit
            a = use
        use = []
        bit //= 2
        
    print(ans)

if __name__ == "__main__":
    main()