1
#define ll long long
2
const int MOD = 1e9 + 7;
3

4
class Solution {
5
 public:
6
  ll summation(ll n) {
7
    return (n * (n + 1) / 2);
8
  }
9

10
  int maxProfit(vector<int> &inventory, int orders) {
11
    ll n = inventory.size(), i = 0, ans = 0;
12
    inventory.push_back(0);
13
    sort(inventory.rbegin(), inventory.rend());
14
    while (orders and i < n) {
15
      if (inventory[i] != inventory[i + 1]) {
16
        ll width = i + 1, h = inventory[i] - inventory[i + 1];
17
        ll available = width * h, gain = 0;
18
        if (available <= orders) {
19
          orders -= available;
20
          // from each of the first i+1 inventories, we gain (inventory[i+1] +
21
          // 1) + ... + inventory[i] value
22
          gain = (width * (summation(inventory[i]) - summation(inventory[i + 1]))) % MOD;
23
        } else {
24
          ll q = orders / width, r = orders % width;
25
          // q balls picked from each of the first i+1 inventories
26
          gain = (width * (summation(inventory[i]) - summation(inventory[i] - q))) % MOD;
27
          // 1 ball picked from r inventories providing value (inventory[i]-q)
28
          gain = (gain + r * (inventory[i] - q)) % MOD;
29
          orders = 0;
30
        }
31

32
        ans = (ans + gain) % MOD;
33
      }
34

35
      i++;
36
    }
37

38
    return ans;
39
  }
40
};