3117. Minimum Sum of Values by Dividing Array Hard

1/**
2 * [3117] Minimum Sum of Values by Dividing Array
3 *
4 * You are given two arrays nums and andValues of length n and m respectively.
5 * The value of an array is equal to the last element of that array.
6 * You have to divide nums into m disjoint contiguous <span data-keyword="subarray-nonempty">subarrays</span> such that for the i^th subarray [li, ri], the bitwise AND of the subarray elements is equal to andValues[i], in other words, nums[li] &amp; nums[li + 1] &amp; ... &amp; nums[ri] == andValues[i] for all 1 <= i <= m, where &amp; represents the bitwise AND operator.
7 * Return the minimum possible sum of the values of the m subarrays nums is divided into. If it is not possible to divide nums into m subarrays satisfying these conditions, return -1.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,4,3,3,2], andValues = [0,3,3,2]</span>
12 * Output: <span class="example-io">12</span>
13 * Explanation:
14 * The only possible way to divide nums is:
15 * <ol>
16 * 	[1,4] as 1 &amp; 4 == 0.
17 * 	[3] as the bitwise AND of a single element subarray is that element itself.
18 * 	[3] as the bitwise AND of a single element subarray is that element itself.
19 * 	[2] as the bitwise AND of a single element subarray is that element itself.
20 * </ol>
21 * The sum of the values for these subarrays is 4 + 3 + 3 + 2 = 12.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">nums = [2,3,5,7,7,7,5], andValues = [0,7,5]</span>
26 * Output: <span class="example-io">17</span>
27 * Explanation:
28 * There are three ways to divide nums:
29 * <ol>
30 * 	[[2,3,5],[7,7,7],[5]] with the sum of the values 5 + 7 + 5 == 17.
31 * 	[[2,3,5,7],[7,7],[5]] with the sum of the values 7 + 7 + 5 == 19.
32 * 	[[2,3,5,7,7],[7],[5]] with the sum of the values 7 + 7 + 5 == 19.
33 * </ol>
34 * The minimum possible sum of the values is 17.
35 * </div>
36 * <strong class="example">Example 3:
37 * <div class="example-block">
38 * Input: <span class="example-io">nums = [1,2,3,4], andValues = [2]</span>
39 * Output: <span class="example-io">-1</span>
40 * Explanation:
41 * The bitwise AND of the entire array nums is 0. As there is no possible way to divide nums into a single subarray to have the bitwise AND of elements 2, return -1.
42 * </div>
43 *  
44 * Constraints:
45 * 
46 * 	1 <= n == nums.length <= 10^4
47 * 	1 <= m == andValues.length <= min(n, 10)
48 * 	1 <= nums[i] < 10^5
49 * 	0 <= andValues[j] < 10^5
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array/
55// discuss: https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn minimum_value_sum(nums: Vec<i32>, and_values: Vec<i32>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3117() {
73    }
74}
75