Overview

This problem asks us to maximize the product (harvest) of all elements, given \(N\) elements (initial growth levels \(A_i\) of fruit trees) whose total sum is increased by exactly \(K\).

To maximize the product, the optimal strategy is “prioritize increasing smaller elements to make all values as equal as possible.” By leveraging this property and combining binary search with fast exponentiation, we can efficiently determine the optimal distribution even for extremely large values of \(K\).

---

Analysis

1. Optimal Strategy for Maximizing the Product

Given two variables \(x, y\) with a fixed sum \(x + y = S\), the product \(x \times y\) becomes larger as the difference between \(x\) and \(y\) decreases. For example, when the sum is \(10\): - \(2 \times 8 = 16\) - \(5 \times 5 = 25\) (this is larger)

This property holds for \(N\) variables as well. Therefore, when distributing fertilizer, the greedy choice of “prioritize giving fertilizer to the tree with the currently lowest growth level” is optimal.

2. Naive Approach and Its Limitations

By repeating the operation “give 1 bag of fertilizer to the smallest element” \(K\) times, we can simulate the optimal distribution. However, under the given constraints where \(K \le 10^{18}\), simulating one step at a time would result in a Time Limit Exceeded (TLE) verdict.

3. Solution Using Binary Search

Instead, we change our perspective and consider the decision problem: “Can we make all trees have a final growth level of at least \(X\)?”

The total amount of fertilizer needed to raise all trees with growth level below \(X\) up to \(X\) is: $\( \sum_{i=1}^{N} \max(0, X - A_i) \)\( If this is at most \)K\(, then it is possible to make all trees have a growth level of at least \)X$.

Since the required total fertilizer is monotonically increasing with respect to \(X\) (the larger \(X\) is, the more fertilizer is needed), we can use Binary Search to efficiently find “the maximum \(X\) such that all trees can be raised to at least \(X\).”

4. Distributing Remaining Fertilizer

After finding the maximum \(X\), there may still be leftover fertilizer. Let \(R\) be the number of remaining bags of fertilizer. It is optimal to distribute these \(R\) bags one each to \(R\) of the trees that have growth level \(X\) (raising their growth level to \(X + 1\)).

---

Algorithm

1. Determine the target value \(X\) using binary search

   • Set the search range to low = 1, high = 2 * 10^18.
   • For the midpoint mid, calculate the total fertilizer needed to raise all \(A_i\) to at least mid.
   • If the total is at most \(K\), we might be able to achieve a larger value, so set low = mid + 1; otherwise, set high = mid - 1.

2. Calculate the remaining fertilizer \(R\)

   • For the determined maximum \(X\) (denoted ans_X in the code), calculate the total fertilizer \(S\) actually consumed to raise all trees to at least \(X\).
   • The remaining fertilizer is \(R = K - S\).

3. Calculate the final product (answer)

   • Trees with original growth level greater than \(X\) (\(A_i > X\)) receive no fertilizer and remain at \(A_i\).
   • Trees with original growth level at most \(X\) (\(A_i \le X\)) are all raised to growth level \(X\).
   • Among those, \(R\) trees receive one extra bag of fertilizer, bringing their growth level to \(X + 1\), while the rest remain at \(X\).
   • Multiply all these values together and compute the result modulo \(10^9 + 7\). For parts where the same value is multiplied many times, use fast exponentiation (repeated squaring) for efficient computation.

---

Complexity

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

  • Each binary search check requires an \(O(N)\) loop. The number of binary search iterations is at most \(\log_2(2 \times 10^{18}) \approx 61\), so this part is sufficiently fast.
  • The final product calculation is \(O(N + \log N)\).
  • Overall, this comfortably fits within the time limit.

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

  • Memory is consumed only for the array storing the initial growth levels \(A_i\) of each tree.

---

Implementation Notes

• Preventing Overflow When computing the total fertilizer needed during binary search, simply accumulating the sum may temporarily exceed the maximum value of long long (overflow). In the code, instead of checking sum + (mid - A[i]) > K, we rearrange it to mid - A[i] > K - sum for safe comparison, preventing overflow.

• Fast Exponentiation Using Repeated Squaring Since we need to multiply the same value \(X\) or \(X+1\) a large number of times, a power function (repeated squaring) is implemented to compute this in \(O(\log N)\).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to calculate (base^exp) % mod
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Binary search to find the maximum possible minimum growth level X
    long long low = 1;
    long long high = 2000000000000000000LL; // 2 * 10^18, safe upper bound
    long long ans_X = 1;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        long long sum = 0;
        bool ok = true;
        for (int i = 0; i < N; ++i) {
            if (mid > A[i]) {
                // Safe overflow check for sum + (mid - A[i]) > K
                if (mid - A[i] > K - sum) {
                    ok = false;
                    break;
                }
                sum += mid - A[i];
            }
        }
        if (ok) {
            ans_X = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // Calculate the exact amount of fertilizer used to bring all elements to at least ans_X
    long long S = 0;
    for (int i = 0; i < N; ++i) {
        if (ans_X > A[i]) {
            S += ans_X - A[i];
        }
    }
    long long R = K - S; // Remaining fertilizer to distribute

    long long MOD = 1000000007;
    long long ans = 1;
    long long count_le = 0;

    // Separate elements that are strictly greater than ans_X
    for (int i = 0; i < N; ++i) {
        if (A[i] > ans_X) {
            ans = (ans * (A[i] % MOD)) % MOD;
        } else {
            count_le++;
        }
    }

    // Out of count_le elements that became ans_X, R of them will be incremented to ans_X + 1
    long long term1 = power(ans_X, count_le - R, MOD);
    long long term2 = power(ans_X + 1, R, MOD);

    ans = (ans * term1) % MOD;
    ans = (ans * term2) % MOD;

    cout << ans << "\n";

    return 0;
}

---

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