2931. Maximum Spending After Buying Items Hard

1/**
2 * [2931] Maximum Spending After Buying Items
3 *
4 * You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the j^th item in the i^th shop has a value of values[i][j]. Additionally, the items in the i^th shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.
5 * On each day, you would like to buy a single item from one of the shops. Specifically, On the d^th day you can:
6 * 
7 * 	Pick any shop i.
8 * 	Buy the rightmost available item j for the price of values[i][j] * d. That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] * d.
9 * 
10 * Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.
11 * Return the maximum amount of money that can be spent on buying all  m * n products.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: values = [[8,5,2],[6,4,1],[9,7,3]]
16 * Output: 285
17 * Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1.
18 * On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4.
19 * On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9.
20 * On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16.
21 * On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25.
22 * On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36.
23 * On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49.
24 * On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64.
25 * On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81.
26 * Hence, our total spending is equal to 285.
27 * It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products. 
28 * 
29 * <strong class="example">Example 2:
30 * 
31 * Input: values = [[10,8,6,4,2],[9,7,5,3,2]]
32 * Output: 386
33 * Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2.
34 * On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4.
35 * On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9.
36 * On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16.
37 * On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25.
38 * On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36.
39 * On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49.
40 * On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64
41 * On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81.
42 * On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100.
43 * Hence, our total spending is equal to 386.
44 * It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.
45 * 
46 *  
47 * Constraints:
48 * 
49 * 	1 <= m == values.length <= 10
50 * 	1 <= n == values[i].length <= 10^4
51 * 	1 <= values[i][j] <= 10^6
52 * 	values[i] are sorted in non-increasing order.
53 * 
54 */
55pub struct Solution {}
56
57// problem: https://leetcode.com/problems/maximum-spending-after-buying-items/
58// discuss: https://leetcode.com/problems/maximum-spending-after-buying-items/discuss/?currentPage=1&orderBy=most_votes&query=
59
60// submission codes start here
61
62impl Solution {
63    pub fn max_spending(values: Vec<Vec<i32>>) -> i64 {
64        
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_2931() {
76    }
77}
78