Show problems as
Classic problem #1648MediumArrayMathBinary SearchGreedySortingHeap (Priority Queue)

Sell Diminishing-Valued Colored Balls

Real-world version: Rare Poster Revenue
Tracked in this browser only
Read Sell Diminishing-Valued Colored Balls on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A poster archive prices reprints by scarcity. stacks[i] is how many copies of design i are left in the drawer, and a copy of a design that still has k copies in the drawer sells for exactly k credits, after which that design has k - 1 copies left.

A wholesaler has paid for orders copies in total and does not care which designs they come from, so you choose the design each copy is drawn from, one copy at a time.

Return the largest total number of credits the archive can take in, modulo 10^9 + 7.

Examples

Example 1

Input
stacks = [2, 5], orders = 4
Output
14

Draw from design 1 at 5, 4 and 3 credits, then from design 0 at 2 credits, for 14 credits in total.

Example 2

Input
stacks = [3, 5], orders = 6
Output
19

Draw from design 1 at 5 and 4 credits, then from design 0 at 3 credits, then design 1 at 3, then design 0 at 2, then design 1 at 2, for 19 credits.

Example 3

Input
stacks = [4, 4, 4], orders = 5
Output
18

Draw one copy of each design at 4 credits, then two more copies at 3 credits each, for 18 credits.

Example 4

Input
stacks = [7], orders = 7
Output
28

Only one design exists, so its copies go at 7, 6, 5, 4, 3, 2 and 1 credits.

Constraints

  • 1 <= stacks.length <= 10^5
  • 1 <= stacks[i] <= 10^9
  • 1 <= orders <= min(sum(stacks[i]), 10^9)

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_profit(stacks: list[int], orders: int) -> int:
Java
public int maxProfit(int[] stacks, int orders)

More on the same topics