Overview

This problem asks us to determine how to distribute a total of \(K\) bags of fertilizer to maximize the product of the growth values of fruit trees.

We utilize the property that “to maximize the overall product, it is optimal to prioritize raising the lowest growth values, bringing all values as close to equal as possible” (an intuitive property of the AM-GM inequality). Since \(K\) can be very large, we use binary search to efficiently find the final lower bound of the growth values.

Analysis

1. Optimal Strategy for Maximizing the Product

When the sum of two variables \(x, y\) is constant (\(x + y = S\)), their product \(xy\) is larger when the difference between \(x\) and \(y\) is smaller (i.e., when they are as close to equal as possible). This property holds even when there are \(N\) variables. Therefore, the optimal strategy for distributing fertilizer is a greedy approach: “Give fertilizer to the tree with the currently lowest growth value to raise the overall minimum.”

2. Limitations of Simple Simulation

Repeating the operation “give one bag of fertilizer to the tree with the lowest growth value” \(K\) times would yield the optimal solution, but looking at the constraints, \(K \le 10^{18}\). Simulating one bag at a time would exceed the time limit (TLE).

3. Speeding Up with Binary Search

Instead, we consider the decision problem: “Is it possible to make all fruit trees have a growth value of at least \(X\)?”

The total amount of fertilizer needed to raise all trees with growth value less than \(X\) to exactly \(X\) is: $\( \sum_{A_i < X} (X - A_i) \)\( If this required total is at most \)K\(, then it is possible to make all trees have a growth value of at least \)X$.

Since this required amount increases monotonically with respect to \(X\), we can use binary search to efficiently find “the maximum \(X\) such that all trees can have a growth value of at least \(X\).”

Algorithm

1. Sorting and Prefix Sum Preparation Sort the initial growth values \(A\) of the fruit trees in ascending order. Also, create a prefix sum array pref to efficiently compute the sum of elements less than a given value \(X\).

2. Determining the Lower Bound \(X\) via Binary Search Implement a function check(X) that determines “whether all fruit trees can have a growth value of at least \(X\).”

   • Use binary search (bisect_left) to find the number idx of trees with \(A_i < X\).
   • The amount of fertilizer needed to raise all those trees to \(X\) is computed as idx * X - pref[idx].
   • Return True if this is at most \(K\), otherwise return False.

Using this decision function, find the maximum achievable \(X\) via binary search.

1. Distributing Remaining Fertilizer and Computing the Final Product After raising all trees to at least \(X\), there may still be rem = K - (required fertilizer) bags remaining. These remaining rem bags are distributed one by one to trees that have growth value \(X\), raising their growth value to \(X+1\).

The final growth values of the trees are as follows: - Among the trees that were originally at most \(X\) (\(C\) trees in total), rem of them become \(X+1\), and the remaining \(C - rem\) trees stay at \(X\). - Trees that originally had a growth value greater than \(X\) remain unchanged at their initial values.

Compute the product of all these values modulo \(10^9 + 7\) cumulatively and output the result.

Complexity

• Time Complexity: \(O(N \log N + \log N \log(\max A_i + K))\)

  • Sorting the initial array takes \(O(N \log N)\).
  • The number of binary search iterations is \(O(\log(\max A_i + K))\), and each iteration performs a bisect_left taking \(O(\log N)\).
  • The final product computation is \(O(N + \log K)\).
  • Overall, this comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used to store the sorted array \(A\) and the prefix sum array pref.

Implementation Notes

• Judgment Using True Values: The maximization judgment must be performed using true values before taking the modulo \(10^9+7\). Therefore, during the binary search, calculations are done without taking the remainder by MOD.

• Distinguishing Between bisect_left and bisect_right:

  • bisect_left(A, X): Used to find the number of elements less than \(X\) (the number of trees that need to be raised).

  • bisect_right(A, X): Used to find the number of elements at most \(X\) (the total number \(C\) of trees whose growth value becomes \(X\) after raising).

    Source Code

import sys
from bisect import bisect_left, bisect_right

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    A.sort()
    
    pref = [0] * (N + 1)
    for i in range(N):
        pref[i+1] = pref[i] + A[i]
        
    def check(X):
        idx = bisect_left(A, X)
        cost = idx * X - pref[idx]
        return cost <= K

    ok = 1
    ng = 10**9 + K + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
            
    X = ok
    idx = bisect_left(A, X)
    cost = idx * X - pref[idx]
    rem = K - cost
    
    C = bisect_right(A, X)
    
    MOD = 10**9 + 7
    
    ans = pow(X + 1, rem, MOD) * pow(X, C - rem, MOD) % MOD
    
    for i in range(C, N):
        ans = ans * A[i] % MOD
        
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.