Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is very happy today because he got an offer from Gordon Ramsay himself to work for him in London. Chef wants to prepare a delicious cake for Gordon to impress him, but he does not know that Gordon Ramsay is not easy to impress.

Gordon cut Chef's cake into $N$ small slices (numbered $1$ through $N$), placed in a row in such a way that for each valid $i$, slices $i$ and $i+1$ are adjacent. Note that slices $N$ and $1$ are not adjacent. For each valid $i$, the $i$-th slice has *taste* $A_{i}$. Gordon wants to put special toppings on some slices and then ask Chef to group all slices into $K$ clusters in such a way that the slices in each cluster form a contiguous sequence and the *sweetness* of the cake is maximum possible.

For each valid $i$, let's denote the topping on the $i$-th slice by $t_{i}$ ($t_{i} = 0$ if there is no topping on this slice); the *sweetness* of this slice is $t_{i} \cdot A_{i}$, so the sweetness of a slice without any special topping is $0$.

The sweetness of a cluster is the total (summed up) sweetness of all slices in this cluster. Let's denote the sweetnesses of all clusters by $S_{1}, S_{2}, \ldots, S_{K}$. The sweetness of the whole cake is computed as $S_{1} * S_{2} * \ldots * S_{K}$, where the operation $*$ is defined in the following way: for any non-negative integers $x$ and $y$ such that $x ≥ y$,
$$x * y = y * x = \sum_{n=0}^{\lfloor\log_{2}(x)\rfloor} 2^{n}(\lfloor\frac{x}{2^{n}}\rfloor \bmod 2)(\lfloor\frac{y}{2^{n}}\rfloor \bmod 2) \,.$$
It can be proven that this operation is associative, i.e. $(x * y) * z = x * (y * z)$.

You should answer $Q$ queries. In each query, you are given the toppings on all slices and the number of clusters $K$. Tell Chef the maximum possible sweetness of the cake!

------  Input ------
The first line of the input contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The next line contains a single integer $Q$.
For each query, two lines follow. The first of these lines contains a single integer $K$. The second line contains $N$ space-separated integers $t_{1}, t_{2}, \ldots, t_{N}$.

------  Output ------
Print a single line containing one integer — the maximum sweetness.

------  Constraints ------
$1 ≤ Q ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{15}$ for each valid $i$
$0 ≤ t_{i} ≤ 10$ for each valid $i$
in each query, the number of slices with toppings does not exceed $50$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
10
15 5 26 4 3 13 5 5 27 11
2
3
2 3 1 4 7 1 5 1 1 1
1
0 0 0 0 0 0 0 1 0 0
----- Sample Output 1 ------ 
33
5
----- explanation 1 ------ 
For the first query, Chef can choose clusters in the following way: cluster $1$ contains slices $1$ and $2$, cluster $2$ contains slices $3$ through $7$ and cluster $3$ contains slices $8$ through $10$. The sweetness of the cake is $(15 \cdot 2 + 5 \cdot 3) * (26 \cdot 1 + 4 \cdot 4 + 3 \cdot 7 + 13 \cdot 1 + 5 \cdot 5) * (5 \cdot 1 + 27 \cdot 1 + 11 \cdot 1) = 33$.

Difficulty: HARD
Tags: Bit manipulation

Sorting

Complete search

Dynamic programming

Mathematics
Skill types: Dynamic programming

Bit manipulation

Sorting

Complete search

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	k = int(input())
	slices = list(filter(lambda x: x, map(lambda x: x[0] * x[1], zip(a, map(int, input().split())))))
	nn = len(slices)
	if k > nn:
		print(0)
		continue
	b = 64
	bm = 0
	p_sum = [slices[0]]
	for i in range(1, nn):
		p_sum.append(slices[i] + p_sum[-1])
	dp = [[False] * k for __ in range(nn)]
	while b > -1:
		bm = bm | 1 << b
		for cn in range(nn):
			dp[cn][0] = p_sum[cn] & bm == bm
			for ck in range(1, k):
				dp[cn][ck] = False
		for cn in range(nn):
			for ck in range(1, k):
				for pn in range(cn):
					dp[cn][ck] = dp[cn][ck] or (dp[pn][ck - 1] and p_sum[cn] - p_sum[pn] & bm == bm)
		if not dp[-1][-1]:
			bm -= 1 << b
		b -= 1
	print(bm)


n = int(input())
taste = list(map(int, input().split()))
q = int(input())
from functools import lru_cache

def solve(taste, sweet):
	g = [i * j for (i, j) in zip(taste, sweet) if i * j]
	size = len(g)
	ans = 0

	@lru_cache(None)
	def dp(i, k, bit):
		if i == size:
			return k == 0
		s = r = 0
		for j in range(i, size):
			s += g[j]
			if s & 1 << bit and s & ans >= ans:
				r |= dp(j + 1, k - 1, bit)
		return r
	for bit in range(64, -1, -1):
		ans |= dp(0, k, bit) << bit
	return ans
for _ in range(q):
	k = int(input())
	sweet = list(map(int, input().split()))
	print(solve(taste, sweet))


def group(S, k):
	if k == 1:
		return sum(S)
	firstPiece = 0
	answer = 0
	dynamic = {}
	for i in range(len(S) - k + 1):
		firstPiece += S[i]
		answer = max(groupWithPattern(S[i + 1:], k - 1, firstPiece, dynamic), answer)
	return answer

def groupWithPattern(S, k, p, dynamic):
	if k == 1:
		return sum(S) & p
	try:
		return dynamic[len(S), k, p]
	except KeyError:
		pass
	firstPiece = 0
	answer = 0
	for i in range(len(S) - k + 1):
		firstPiece += S[i]
		answer = max(groupWithPattern(S[i + 1:], k - 1, p & firstPiece, dynamic), answer)
	dynamic[len(S), k, p] = answer
	return answer
n = int(input())
A = [int(a) for a in input().split()]
q = int(input())
for _ in range(q):
	k = int(input())
	T = [int(t) for t in input().split()]
	S = [a * t for (a, t) in zip(A, T) if a * t > 0]
	print(group(S, k) if k <= len(S) else 0)


from sys import *
import os
import re
from math import *
from bisect import *
from collections import defaultdict
import functools

def nextline():
	return list(map(int, input().strip().split()))
N = int(input())
A = nextline()
Q = int(input())
for q in range(Q):
	(K,) = nextline()
	t = nextline()
	values = []
	for i in range(N):
		v = t[i] * A[i]
		if v == 0:
			continue
		values.append(v)
	M = len(values)
	if K > M:
		print(0)
		continue
	if K == M:
		print(functools.reduce(lambda a, b: a & b, values))
		continue
	DP = [None] * (M + 1)
	DP[0] = set()
	presum = [0] * (M + 1)
	for i in range(M):
		presum[i + 1] = presum[i] + values[i]
		DP[i + 1] = {presum[i + 1]}
	for p in range(2, K + 1):
		DPM1 = DP
		DP = [set() for x in range(M + 1)]
		for i in range(p, M + 1):
			for j in range(p - 1, i):
				partsum = presum[i] - presum[j]
				for v in DPM1[j]:
					DP[i].add(partsum & v)
	print(max(DP[M]))