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: Time Limit Exceeded

Solution code:
def b_len(v):
    return len(bin(v)[2:])


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

cs = [0]
for aa in a:
    cs.append(cs[-1] + aa)

ps = []
for i in range(1, n + 1):
    for j in range(i):
        ps.append(cs[i] - cs[j])

ps = sorted(ps, reverse=True)

pw = b_len(ps[k - 1])
MOD = 2 ** pw

nps = [set() for _ in range(pw)]
for i in range(len(ps)):
    t = ps[i] % MOD
    for j in range(pw):
        if 1 << j & t:
            nps[j].add(i)

ans = 0
buf = set(range(len(ps)))
for j in range(pw)[::-1]:
    if len(nps[j]) >= k:
        x = buf & nps[j]
        if len(x) >= k:
            buf = x
            ans += 2 ** j

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import itertools


def list_subarray_sums(arr):
    for start in range(len(arr)):
        for end in range(start + 1, len(arr) + 1):
            yield sum(arr[start:end])


def logical_and(arr, idx=0, current=0):
    if idx >= len(arr):
        return current

    if idx == 0:
        current = arr[0]
    else:
        current = current & arr[idx]

    if current == 0:
        return 0
    return logical_and(arr, idx + 1, current)


if __name__ == '__main__':
    N, K = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))

    sums = set(list_subarray_sums(A))
    combinations = itertools.combinations(sums, K)
    ands = map(lambda arr: logical_and(arr), combinations)
    print(max(ands))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
*a,=map(int,input().split())
l=[]
for i in range(n):
    t=0
    for j in range(i,n):
        t+=a[j]
        l.append(t)
l=sorted(l)[::-1]
m=0
import itertools
for t in itertools.combinations(l,k):
    c=t[0]
    for u in t[1:]:
        c&=u
    m=max(m,c)
print(m)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def ronriseki(a):
    res = a[0]
    for i in a:
        res = res & i
    return res

n, k = map(int, input().split())
a = list(map(int, input().split()))
kirei = [sum(a[i:j]) for i in range(n) for j in range(i + 1, n + 1)]
ans = 0
for i in combinations(kirei, k):
    ans = max(ans, ronriseki(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = list(map(int, input().split()))

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

a_list = []

for i in range(n):
	l = list(itertools.combinations(a, i+1))
	
	a_list += l
	
	
ans = 0


for j in list(itertools.combinations(a_list, k)):
	for y, z in enumerate(j):
		if y == 0:
			tmp = sum(z)
		else:
			tmp &= sum(z)
			
	ans = max(ans, tmp)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

a = np.array(a)

s = 0
e = 0

arr = []
for s in range(N):
    for e in range(s+1, N+1):
        arr.append(a[s:e])

max_len = len(bin(np.sum(a))[2:])

su = 0
b = [bin(np.sum(aa))[2:] for aa in arr]
b = ['0' * (max_len - len(bb)) + bb for bb in b]
while True:
    c = [bb for bb in b if bb[0] == '1']
    if len(c) >= K:
        su += 2 ** (len(c[0]) - 1)
        b = [cc[1:] for cc in c]
    else:
        b = [bb[1:] for bb in b]
    if len(b[0]) == 0:
        break
print(su)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import itertools
import functools

def list_subarray_sums(arr):
    for start in range(len(arr)):
        for end in range(start + 1, len(arr) + 1):
            yield sum(arr[start:end])


if __name__ == '__main__':
    N, K = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))

    sums = set(list_subarray_sums(A))
    ands = map(lambda arr: functools.reduce(lambda x, y: x & y, arr), itertools.combinations(sums, K))
    print(max(ands))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def ronriseki(a):
    res = a[0]
    for i in range(1, len(a)):
        res = res & a[i]
    return res

n, k = map(int, input().split())
a = list(map(int, input().split()))
kirei = set()
for i in range(n):
    for j in range(i + 1, n + 1):
        kirei.add(sum(a[i:j]))
ans = 0
for i in combinations(kirei, k):
    ans = max(ans, ronriseki(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
*a,=map(int,input().split())
l=[]
for i in range(n):
    for j in range(i+1,n+1):
        l.append(sum(a[i:j]))
l=sorted(l)[::-1]
m=0
import itertools
for t in itertools.combinations(l,k):
    c=t[0]
    for u in t[1:]:
        c&=u
    m=max(m,c)
print(m)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))

subsecs = []
S = [0] + list(accumulate(As))
for f in range(1, N+1):
    for t in range(f, N+1):
        subsecs.append(S[t] - S[f-1])

ans = 0
digit = 1 << 40
for d in range(41):
    nsubsecs = []
    for subsec in subsecs:
        if subsec & digit:
            nsubsecs.append(subsec)
    if len(nsubsecs) >= K:
        ans += digit
        subsecs = nsubsecs
    digit >>= 1
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
lis=[]
for i in range(n):
    now=0
    for j in range(i,n):
        now+=a[j]
        lis.append(now)
lis.sort()
bi=[]
mx=40
for i in range(len(lis)):
    num=lis[i]
    keta=[0]*mx

    for j in reversed(range(mx)):
        if num%2==1:
            keta[j]+=1
        num//=2
        if num==0:
            break
    bi.append(keta)

anslis=[]
kouho=set(lis)
for j in range(mx):
    cnt=0
    nxt=set()
    for i in range(len(bi)):
        if not lis[i] in kouho:
            continue
        b=bi[i]
        if b[j]==1:
            cnt+=1
            nxt.add(lis[i])
    if cnt>=k:
        kouho &= nxt

kouho=list(kouho)
ans=kouho[0]
for num in kouho:
    ans &=num
print(ans)

Submission status: Accepted

Solution code:
def dwacon5th_prelims_b():
    n, k = (int(x) for x in input().split())
    A = [int(x) for x in input().split()]
    B = []

    for i in range(n):
        cum = 0
        for a in A[i:]:
            cum += a
            B.append(cum)
    B.sort(reverse=True)

    bit = [0]*41
    cand = B.copy()
    for i in range(40, -1, -1):
        nx = []
        for b in cand:
            if (b >> i) & 1: nx.append(b)
        if len(nx) >= k:
            cand = nx.copy()
            bit[i] = 1

    ans = int(''.join([str(x) for x in reversed(bit)]), base=2)
    print(ans)

if __name__ == '__main__':
   dwacon5th_prelims_b()

Submission status: Accepted

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

l=[]
for i in range(n):
  s=0
  for j in range(i,n):
    s+=a[j]
    l.append(s)
t=0
for i in range(40,-1,-1):
  t+=2**i
  c=0
  for j in l:
    if t==j&t:
      c+=1
  if c<k:
    t-=2**i
print(t)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        tmp = acc[j+1] - acc[i]
        set_ans.add(tmp)
        s = tmp
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(tmp)
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)

Submission status: Accepted

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

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

# 累積和
AS = [0] * (N+1)
for i in range(N):
  AS[i+1] = AS[i] + A[i]
  
# 全要素をリスト化する
B = []
for i in range(N+1):
  for j in range(i+1,N+1):
    wk = AS[j] - AS[i]
    if wk > 0:
      B.append(wk)

ans = 0
for m in range(38,-1,-1):
  cnt = 0
  p = pow(2,m)
  nxt = []
  for b in B:
    if p & b == p:
      nxt.append(b)
  if len(nxt) >= K:
    ans += p
    B = nxt
    # Bの候補が減っていくところがポイント！
  else:
    pass
    # Bは変わらないところがポイント！

print(ans)
#print(B)

Submission status: Accepted

Solution code:
from typing import List, Dict

INF = 10**9+1


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

def remove_if_gt(a, b):
    if a >= b:
        return a-b
    return a

def solve() -> int:
    N, K = read_ints()
    A = read_ints()
    S = []
    for i in range(N):
        prefix = 0
        for j in range(i, N):
            prefix += A[j]
            S.append(prefix)
    S.sort(reverse=True)
    highest_bit = 40
    answer = 0
    while highest_bit >= 0:
        while 1<<highest_bit > S[0]:
            highest_bit -= 1
            if highest_bit < 0:
                return answer
        highest_bit_val = 1<<highest_bit
        count = 0
        for i in range(len(S)):
            if S[i] >= highest_bit_val:
                count += 1
            else:
                break
        if count < K:
            S = [remove_if_gt(s, highest_bit_val) for s in S]
        else:
            answer += highest_bit_val
            S = [remove_if_gt(s, highest_bit_val) for s in S if s >= highest_bit_val]
        S.sort(reverse=True)
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))

n,k = ma()
A = lma()
bu = []
for i in range(n):
    tmp=0
    for j in range(i,n):
        tmp+=A[j]
        bu.append(tmp)
mb = bin(max(bu))
ans = 0
for i in range(len(mb)-3,-1,-1):
    tmp=[]
    for b in bu:
        if (b>>i &1):
            tmp.append(b)
    if len(tmp)>=k:
        ans+=2**i
        bu=tmp
    else:
        pass
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

n,k = ma()
A = lma()
bu = []
for i in range(n):
    tmp=0
    for j in range(i,n):
        tmp+=A[j]
        bu.append(tmp)
mb = bin(max(bu))
ls = [0]*(len(mb)-2)
for b in bu:
    for i in range(len(bin(b))-2):
        if (b>>i &1):
            ls[i]+=1
ans = 0
tmp=bu
for i in range(len(mb)-3,-1,-1):
    if ls[i]<k:
        continue
    tmp2=[]
    for b in tmp:
        if (b>>i &1):
            tmp2.append(b)
    if len(tmp2)>=k:
        ans+=2**i
        tmp=tmp2
    else:
        pass
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n,k=MI()
	A=LI()
	B=[0]
	C=[0]

	for i in A:
		B.append(B[-1]+i)
		C.append(C[-1]^i)
	#print(A,B,C)


	ans=0

	D=[]
	E=[]
	F=[]

	for i in range(n):
		for j in range(i+1,n+1):
			D.append(B[j]-B[i])

	#print(D)

	ans=0

	for i in range(41,-1,-1):
		cnt=0
		E=[]
		for d in D:
			if 1<<i&d:
				E.append(d)
				cnt+=1
				#print(1<<i,d)

		if cnt>=k:
			ans+=1<<i
			D=E.copy()

	print(ans)
	
	









if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(n):
    cur = 0
    for j in range(i, n):
        cur += a[j]
        l.append(cur)
for i in range(40, -1, -1):
    b = 1 << i
    l2 = []
    for j in l:
        if b & j:
            l2.append(j)
    if len(l2) >= k:
        l = l2
a = l[0]
for i in range(1, len(l)):
    a &= l[i]
print(a)

Submission status: Accepted

Solution code:
from copy import copy

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

X=[0]*((N*(N+1))//2)
I=0

for i in range(N):
    S=0
    for j in range(i,N):
        S+=A[j]
        X[I]=S
        I+=1

alpha=max(X)
B=1
while alpha>B:
    B<<=1

P=0
while B>0:
    C=0
    Y=[]
    for a in X:
        if a&B:
            C+=1
            Y.append(a)

    if C>=K:
        P+=B
        X=copy(Y)

    B>>=1

print(P)

Submission status: Accepted

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

import itertools

n, k = map(int, input().split())
a = list(itertools.accumulate(list(map(int, input().split()))))
a = [0] + a
s = [None] * (n*(n+1)//2)
cnt = 0
for i in range(n+1):
    for j in range(i+1,n+1):
        s[cnt] = format(a[j]-a[i], '050b')
        cnt += 1

ret = 0
sel = set(range(n*(n+1)//2))
for i in range(50):
    nxt = set([])
    for j in sel:
        if s[j][i] == '1':
            nxt.add(j)
    if len(nxt)>=k:
        sel = nxt
        ret += 2**(49-i)
print(ret)

Submission status: Accepted

Solution code:
def calc_beauty_list(N, A):
    cumsum = [0 for _ in range(N)]
    cumsum[0] = A[0]
    for n in range(1, N):
        cumsum[n] = cumsum[n - 1] + A[n]
    beauty_list = [0 for _ in range(N * (N + 1) // 2)]
    index = 0
    for left in range(N):
        for right in range(left, N):
            beauty = cumsum[right]
            if left > 0:
                beauty -= cumsum[left - 1]
            beauty_list[index] = beauty
            index += 1
    return beauty_list


def main():
    MAX_BIT = 40
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    beauty_list = calc_beauty_list(N, A)
    # K個の論理積の最大値の計算
    #     2進表記して上位ビットから見ていく（高々数十ビット程度）。
    #     K個以上ビットが立っている桁に当たったら、ビットが立っていない数を消す。
    #         最終桁に行く前にK個になったら、それらの論理積を出して終了。
    #         最終桁まで行き、
    #             それまでK個以上のビットが立ってたことがないなら 0 が答え。
    #             そうでなければ、残っている中から適当にK個選んで論理積を出す。
    usable_flag = [1 for _ in range(N * (N + 1) // 2)]
    found_k_bit = False
    for shift in range(MAX_BIT - 1, -1, -1):
        cnt = len([b for b, u in zip(beauty_list, usable_flag) if u == 1 and (b >> shift & 1 == 1)])
        if cnt >= K:
            found_k_bit = True
            for n, b in enumerate(beauty_list):
                if b >> shift & 1 == 0:
                    usable_flag[n] = 0
        if cnt == K:
            found_k_bit = True
            break
    if not found_k_bit:
        print(0)
    else:
        ans = (1 << MAX_BIT) - 1
        cnt = 0
        for n, b in enumerate(beauty_list):
            if usable_flag[n] == 1 and cnt <= K:
                ans &= b
                cnt += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

beauty = [a[0]]
base = [a[0]]

for ai in a[1:]:
    for i in range(len(base)):
        base[i] += ai
        beauty.append(base[i])
    beauty.append(ai)
    base.append(ai)

ans = 0
for bi in range(41,-1,-1):
    cand = []
    for i in beauty:
        if((i>>bi)&1):
            cand.append(i)
    if(len(cand) >= k):
        ans += 1<<bi
        beauty = cand

print(ans)

Submission status: Accepted

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

A=list(map(int,input().split()))
two=[2**i for i in range(44)][::-1]

sums=[0]
for a in A:
    sums.append(sums[-1]+a)

log=[]

for i in range(N):
    for j in range(i,N+1):
        if sums[j]-sums[i]!=0:
            log.append(sums[j]-sums[i])
log.sort()

ans=0
for t in two:
    count=0
    for item in log:
        if item>=t:
            count+=1
    if count>=K:
        ans+=t
        log=list(filter(lambda x: x>=t, log))
    log=list(map(lambda x: x%t, log))
    

print(ans)

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]
d=[]
for i,x in enumerate(a):
  for y in a[:i]:
    d+=[x-y]
ans=0
t=2**40
for _ in range(41):
  cnt=0
  for j in d:
    cnt+=(ans+t)&j==(ans+t)
  if cnt>=k:ans+=t
  t//=2
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, combinations
from collections import Counter
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A = [0] + list(accumulate(A))
    A = [A[j] - A[i] for i, j in combinations(range(n + 1), 2)]
    C = Counter(A)
    ans = 0
    i = pow(2, 39)
    for _ in range(40):
        cnt = 0
        for key, value in C.items():
            b = ans + i
            if b & key == b: cnt += value
        if cnt >= k: ans += i
        i //= 2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class BIT():
    # A1 ... AnのBIT(1-indexed)
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    # A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    # Ai += x O(logN)
    def update(self, idx, x):
        # print(idx)
        while idx <= self.n:
            # print(idx)
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n, k = getList()
    lis = [0] + getList()
    for i in range(n):
        lis[i+1] += lis[i]

    ka = []
    for i in range(n):
        for j in range(i+1, n+1):
            ka.append(lis[j]-lis[i])

    ans = 0
    for rui in range(50, -1, -1):
        ok = []
        tgt = pow(2, rui)
        for kaka in ka:
            if kaka & tgt == tgt:
                ok.append(kaka)
        if len(ok) >= k:
            ans += tgt
            ka = ok

    print(ans)





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sum_A = sum(A)
    B = [0] + list(accumulate(A))
    cand = []
    for i in range(N+1):
        for j in range(i+1,N+1):
            cand.append(B[j] - B[i])
    ans = 0
    for i in range(40):
        bit = 1 << (39 - i)
        cnt = 0
        new_cand = []
        for c in cand:
            if c & bit:
                cnt += 1
                new_cand.append(c)

        if cnt >= K:
            ans += 2 ** (39 - i)
            cand = new_cand


    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
cusum = [A[0]]
for i in range(1, N):
    cusum += [cusum[-1]+A[i]]
B = []
for i in range(N):
    B += [cusum[i]]
    for j in range(i+1, N):
        B += [cusum[j] - cusum[i]]
max_bit = 43
ans = 0
while max_bit > 0:
    counter = Counter()
    for b in B:
        for i in range(44):
            if b & 1 == 1:
                counter[i] += 1
            b = b >> 1
    for i in range(max_bit, -1, -1):
        if counter[i] >= K:
            filter_bit = 2 ** i
            B = [b for b in B if b & filter_bit == filter_bit]
            max_bit = i-1
            ans += filter_bit
            break
        max_bit = i
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    s = []
    for i in range(n):
        nx = list(accumulate(a[i:]))
        s.extend(nx)

    s.sort()

    first = len(format(s[-1], "b")) - 1
    cur = 0

    for i in range(first, -1, -1):
        x = cur + 2 ** i
        cnt = 0
        for y in s[::-1]:
            if x & y == x:
                cnt += 1
            if x > y:
                break
        if cnt >= k:
            cur = x

    print(cur)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
m = int(math.log2(b[n]))
x = pow(2, m)
s = [[] for _ in range(m + 2)]
for i in range(n):
    for j in range(i + 1, n + 1):
        s[0].append(b[j] - b[i])
c = 0
ans = 0
for i in range(1, m + 2):
    for j in range(len(s[c])):
        if s[c][j] >= x:
            s[i].append(s[c][j] - x)
            s[c][j] -= x
    if len(s[i]) >= k:
        c = i
        ans += x
    x //= 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
a = list(map(int, input().split()))
acc = [0]

for ai in a:
    acc.append(acc[-1]+ai)

l = []

for i in range(N):
    for j in range(i, N):
        l.append(acc[j+1]-acc[i])

ans = 0

for i in range(45):
    nl = []
    
    for li in l:
        if (li>>(44-i))&1:
            nl.append(li)
    
    if len(nl)>=K:
        ans += 2**(44-i)
        l = nl
    
print(ans)

Submission status: Accepted

Solution code:
import bisect
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

SA = [0]
for i in range(N):
    SA.append(SA[-1]+A[i])

C = []
for i in range(N):
    for j in range(i+1, N+1):
        C.append(SA[j]-SA[i])
C.sort()


ans = 0
for i in range(41, -1, -1):
    B = 1 << i
    ind = bisect.bisect_left(C, B)
    if len(C)-ind >= K:
        ans += B
        C = C[ind:]
    for j in range(len(C)):
        C[j] &= B-1
    C.sort()
    # print(i, B, C)
print(ans)

Submission status: Accepted

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

lst = []
for i in range(N):
  lst.append(Xs[i])
  tmp = Xs[i]
  for j in range(i+1,N):
    tmp += Xs[j]
    lst.append(tmp)
  
x = 0
for i in range(40, 0, -1):
  cnt = 0
  t = x + 2**(i-1)
  for l in lst:
    if t&l == t:
      cnt += 1
  if cnt >= K:
    x = t
  
print(x)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    R = [0] + list(accumulate(A))
    subs = []
    for left in range(n + 1):
        for right in range(left + 1, n + 1):
            num = R[right] - R[left]
            subs.append(num)

    for i in reversed(range(41)):
        tmp = []
        for num in subs:
            if num & (1 << i):
                tmp.append(num)
        if len(tmp) >= k:
            subs = tmp

    res = subs[0]
    for num in subs:
        res &= num
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, K = in_nn()
    a = in_nl()
    a_sum = [0] * (N + 1)

    b = set()
    for i in range(N):
        a_sum[i + 1] = a_sum[i] + a[i]

    for i in range(N + 1):
        for j in range(i + 1, N + 1):
            b.add(a_sum[j] - a_sum[i])

    b = sorted(list(b))
    bit = max(b).bit_length()

    ans = 0
    select = set(b)
    for x in range(bit, 0, -1):

        cnt = 0
        t_select = set()
        for tb in select:
            # print(x, tb, (tb >> (x - 1)) & 1)
            if (tb >> (x - 1)) & 1:
                cnt += 1
                t_select.add(tb)

        # print(cnt, select)
        if cnt >= K:
            ans += (1 << (x - 1))
            select = t_select

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b
# 解説見てしまった
# N≤1000の性質をうまく使う必要はない。O(N^2)で全部書き出せばいい。完全に引っ掛け。
# 答えの仮定、bitごとに見る、上位桁からのgreedyらへんがキーワード

from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [sum(A[s:t]) for s, t in combinations(range(N + 1), 2)]

l = max(B).bit_length()  # 何桁扱えば十分か？
x = 0  # 初期値
for i in range(l, -1, -1):  # 上位桁からgreedyに決定
    # 候補のうち i bit目=1がK個以上あれば答えに計上できる
    x_tmp = x + (1 << i)
    if sum((x_tmp & b) == x_tmp for b in B) >= K:  # 確定した桁+i桁を1としたときに答えになり得るか？
        x = x_tmp
print(x)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

C = [0] + list(accumulate(A))
S = []

for i in range(N):
    for j in range(i + 1, N + 1):
        S.append(C[j] - C[i])

for i in range(64)[::-1]:
    tmp = []
    for s in S:
        if (s >> i) & 1:
            tmp.append(s)

    if len(tmp) >= K:
        S = tmp

res = 2**64 - 1

for i in range(K):
    res &= S[i]

print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

C = [0] + list(accumulate(A))
S = []

for i in range(N):
    for j in range(i + 1, N + 1):
        S.append(C[j] - C[i])

for i in range(64)[::-1]:
    tmp = []
    for s in S:
        if (s >> i) & 1:
            tmp.append(s)

    if len(tmp) >= K:
        S = tmp[:]

res = 2**64 - 1

for i in range(K):
    res &= S[i]

print(res)

Submission status: Accepted

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


kouho=[]
for l in range(n):
    kouho.append(a[l])
    tmp=a[l]
    for r in range(l+1,n):
        tmp+=a[r]
        kouho.append(tmp)
kouho.sort()

cnt=0
while 2**cnt<=kouho[-1]:
    cnt+=1

flag=[1]*len(kouho)

while cnt>=0:
    tmp_cnt=0
    for i,item in enumerate(kouho):
        if 2**cnt & item and flag[i]==1:
            tmp_cnt+=1
    if tmp_cnt>=k:
        for i,item in enumerate(kouho):
            if 2**cnt & item and flag[i]==1:
                continue
            else:
                flag[i]=0
    cnt-=1

ans=-1
cnt=0
#print(kouho)
#print(flag)
for i in range(len(kouho)):
    if flag[i]==1:
        cnt+=1
        if ans==-1:
            ans=kouho[i]
        else:
            ans=ans&kouho[i]
    if cnt==k:
        print(ans)
        exit()

Submission status: Accepted

Solution code:
import numpy as np
N, K = [int(_) for _ in input().split()]
A = np.array([0] + [int(_) for _ in input().split()])
C = np.cumsum(A)
X = np.zeros(N * (N + 1) // 2, dtype=int)
il = 0
for l in range(N):
    X[il:il + N - l] = C[l + 1:N + 1] - C[l]
    il += N - l
ans = 0
for i in range(40, -1, -1):
    Y = (X // (2**i) & 1)
    I = Y == 1
    if I.sum() >= K:
        X = X[I]
        ans += 2**i
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def splitbit(n):
    for i in range(61):
        if not n & (1 << i):
            xor_l[i] = 0

N, K = getNM()
A = getList()

imos = copy.deepcopy(A)
imos.insert(0, 0)

for i in range(N):
    imos[i + 1] += imos[i]

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

ans = 0
for i in range(60, -1, -1):
    cnt = 0
    for j in range(len(num)):
        if ans + (2 ** i) & num[j] == ans + (2 ** i):
            cnt += 1
    if cnt >= K:
        # okならフラグを追加する（条件が厳しくなる）
        ans += (2 ** i)
print(ans)