**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Utkarsh Sinha

**Tester:** Zhong Ziqian

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

MEDIUM

**PREREQUISITES**:

DP, bitmasks

**PROBLEM**:

You’re given array A_1,\dots,A_N, you have to split it into K segments to maximize *sweetness* of this partition, which is defined as follows: Firstly each A_i will be multiplied by some number t_i. Then sweetness S_i of each segment is defined as sum of sweetnesses of all elements in it. Sweetness of the whole partition is defined as S_1 * S_2 * \dots * S_k where * is defined as follows:

You will have Q queries with given t_i for each query, constraints:

- 1 \leq Q \leq 10
- 1 \leq K, N \leq 10^5
- 1 \leq A_i \leq 10^{15}
- 0 \leq t_i \leq 10
- At most 50 of t_i will
*not*be equal to zero.

**QUICK EXPLANATION**:

Just a bit of bit magic and observations.

**EXPLANATION**:

You may immediately recognize that x*y is simply bitwise and of x and y. Then you should note that there is no reason to have any segment with sweetness 0, thus we may simply ignore all indexes i having t_i = 0 and assume that N \leq 50. Let’s deal with the following subproblem: Given number mask you have to check if there’s a partition such that mask is a submask of its sweetness. It may be done via simple DP in O(m^2 k):

```
bool check(vector<int> a, int mask, int k) {
int m = a.size();
int dp[m + 1][k + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= m; i++) {
int sum = 0;
for(int j = i; j > 0; j--) {
sum += a[j - 1];
if((sum & mask) == mask) {
for(int t = 1; t <= k; t++) {
dp[i][t] |= dp[j - 1][t - 1];
}
}
}
}
return dp[m][k];
}
```

With this function we may greedily check bits in answer and set them to 1 whenever possible. Assume that ta is the array of non-zero t_i A_i, then solution looks like this:

```
if(k > ta.size()) {
cout << 0 << "\n";
} else {
int l = 0, r = 1LL << 55;
while(r - l > 1) {
int m = (l + r) / 2;
if(check(ta, m, k)) {
l = m;
} else {
r = m;
}
}
cout << l << endl;
}
```

Note that though we used binary search here, function is not monotonic in common sense but it’s monotonic in terms of logic functions, that is if u is submask of v then f(u) \leq f(v). Turns out it’s also enough to utilize simple binary search in particular case of l=0 and r=2^k and it will find lexicographically largest mask on which check is equal to 1.

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.