Welcome to Subscribe On Youtube
2931. Maximum Spending After Buying Items
Description
You are given a 0indexed 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 nonincreasing order of value. That is, values[i][j] >= values[i][j + 1]
for all 0 <= j < n  1
.
On each day, you would like to buy a single item from one of the shops. Specifically, On the d^{th}
day you can:
 Pick any shop
i
.  Buy the rightmost available item
j
for the price ofvalues[i][j] * d
. That is, find the greatest indexj
such that itemj
was never bought before, and buy it for the price ofvalues[i][j] * d
.
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.
Return the maximum amount of money that can be spent on buying all m * n
products.
Example 1:
Input: values = [[8,5,2],[6,4,1],[9,7,3]] Output: 285 Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1. On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4. On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9. On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16. On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25. On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36. On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49. On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64. On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81. Hence, our total spending is equal to 285. It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products.
Example 2:
Input: values = [[10,8,6,4,2],[9,7,5,3,2]] Output: 386 Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2. On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4. On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9. On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16. On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25. On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36. On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49. On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64 On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81. On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100. Hence, our total spending is equal to 386. It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.
Constraints:
1 <= m == values.length <= 10
1 <= n == values[i].length <= 10^{4}
1 <= values[i][j] <= 10^{6}
values[i]
are sorted in nonincreasing order.
Solutions

class Solution { public long maxSpending(int[][] values) { int m = values.length, n = values[0].length; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) > a[0]  b[0]); for (int i = 0; i < m; ++i) { pq.offer(new int[] {values[i][n  1], i, n  1}); } long ans = 0; for (int d = 1; !pq.isEmpty(); ++d) { var p = pq.poll(); int v = p[0], i = p[1], j = p[2]; ans += (long) v * d; if (j > 0) { pq.offer(new int[] {values[i][j  1], i, j  1}); } } return ans; } }

class Solution { public: long long maxSpending(vector<vector<int>>& values) { priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; int m = values.size(), n = values[0].size(); for (int i = 0; i < m; ++i) { pq.emplace(values[i][n  1], i, n  1); } long long ans = 0; for (int d = 1; pq.size(); ++d) { auto [v, i, j] = pq.top(); pq.pop(); ans += 1LL * v * d; if (j) { pq.emplace(values[i][j  1], i, j  1); } } return ans; } };

class Solution: def maxSpending(self, values: List[List[int]]) > int: n = len(values[0]) pq = [(row[1], i, n  1) for i, row in enumerate(values)] heapify(pq) ans = d = 0 while pq: d += 1 v, i, j = heappop(pq) ans += v * d if j: heappush(pq, (values[i][j  1], i, j  1)) return ans

func maxSpending(values [][]int) (ans int64) { pq := hp{} n := len(values[0]) for i, row := range values { heap.Push(&pq, tuple{row[n1], i, n  1}) } for d := 1; len(pq) > 0; d++ { p := heap.Pop(&pq).(tuple) ans += int64(p.v * d) if p.j > 0 { heap.Push(&pq, tuple{values[p.i][p.j1], p.i, p.j  1}) } } return } type tuple struct{ v, i, j int } type hp []tuple func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i].v < h[j].v } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) } func (h *hp) Pop() any { a := *h; v := a[len(a)1]; *h = a[:len(a)1]; return v }

function maxSpending(values: number[][]): number { const m = values.length; const n = values[0].length; const pq = new PriorityQueue({ compare: (a, b) => a[0]  b[0] }); for (let i = 0; i < m; ++i) { pq.enqueue([values[i][n  1], i, n  1]); } let ans = 0; for (let d = 1; !pq.isEmpty(); ++d) { const [v, i, j] = pq.dequeue()!; ans += v * d; if (j > 0) { pq.enqueue([values[i][j  1], i, j  1]); } } return ans; }