\(i,j\) に対して、\(A _ i+B _ i+2\le A _ j+B _ j\) が成り立つとき、\[\begin{aligned}(A _ i+B _ i+1)(A _ j+B _ j-1)&=(A _ i+B _ i)(A _ j+B _ j)-(A _ i+B _ i)+(A _ j+B _ j)-1\\&=(A _ i+B _ i)(A _ j+B _ j)+(A _ j+B _ j-(A _ i+B _ i+1))\\&\gt(A _ i+B _ i)(A _ j+B _ j)\end{aligned}\] が成り立ちます。 この式から、\(A _ i+B _ i+2\le A _ j+B _ j\) かつ \(B _ j\gt0\) なら \(B _ i\) を \(1\) 増やして \(B _ j\) を \(1\) 減らすことで収穫量が増えることがわかります。 最適な配分において \(A _ i+B _ i+2\le A _ j+B _ j\) が成り立つなら \(B _ j=0\) でなければなりません。

よって、最適な配分においてある正整数 \(X\) が存在して、それぞれの果樹は以下のいずれかの条件を満たします。

• \(A _ i+B _ i=X\)
• \(A _ i+B _ i=X+1\)
• \(A _ i\ge X+2\wedge B _ i=0\)

この事実から、次のような解法を考えることができます。

• \(X\) の値を二分探索で求める
  • 正整数 \(k\) に対して、上の条件を満たし \(k\le X\) となるような \(X\) が存在することは、\(A _ i\lt X+2\) を満たす \(A _ i\) の個数 \(C\) と総和 \(S\) について \(Ck\le S+K\) が成り立つことと同値です。これを利用することで \(O(N\log K)\) で \(X\) の値を求めることができます。列 \((A _ i) _ {1\le i\le N}\) をソートし、\(A _ i\ge X+2\) を満たす \(A _ i\) の個数について二分探索を行うと \(O(N\log N)\) 時間とすることができます。Quick Select のアルゴリズムを少し変形することで、これを \(O(N)\) 時間にすることもできます。
• 具体的に配分を行うアルゴリズムを考え、それを高速化する
  • 「現在の成長度が最小である果樹をひとつ選び、肥料を \(1\) 与える。」という操作を \(K\) 回繰り返すことで最適な配分が得られることがわかります。\(K\) 回の操作を愚直に行うと実行時間制限に間に合いませんが、最小ヒープなどを使った上で同じ成長度の果樹への操作をまとめることによって、\(O(N\log N)\) 時間とすることができます。

どちらの解法も十分高速です。

実装例は以下のようになります。

#include <iostream>
#include <queue>
#include <atcoder/modint>
using namespace std;
using modint = atcoder::static_modint<1000000007>;

int main() {
    int N;
    long K;
    cin >> N >> K;

    // (現在の成長度, 個数) をヒープで管理する
    priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
    // 番兵として十分大きな成長度の果樹を入れておく
    pq.emplace(1000000001000000001, 0);

    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        pq.emplace(A, 1);
    }

    // K 袋配り切るまで操作を行う
    while (K) {
        // 成長度最小の果樹を選び
        auto [A, count] = pq.top();
        pq.pop();
        if (K / count >= pq.top().first - A) { // 次の成長度に追いつけるなら追いつくまで配る
            K -= (pq.top().first - A) * count;
            auto [next_A, next_count]{pq.top()};
            pq.pop();
            pq.emplace(next_A, count + next_count);
        } else { // 追いつけないならあるだけ配る
            pq.emplace(A + K / count + 1, K % count);
            pq.emplace(A + K / count, count - K % count);
            K = 0;
        }
    }

    // 答えを求める
    modint ans = 1;
    while (!empty(pq)) {
        auto [A, count] = pq.top();
        pq.pop();
        ans *= modint{A}.pow(count);
    }
    cout << ans.val() << endl;
    return 0;
}

from heapq import heappush, heappop


N, K = map(int, input().split())

# (現在の成長度, 個数) をヒープで管理する
pq = []
# 番兵として十分大きな成長度の果樹を入れておく
heappush(pq, (1000000001000000001, 0))

for A in map(int, input().split()):
    heappush(pq, (A, 1))

# K 袋配り切るまで操作を行う
while K > 0:
    A, count = heappop(pq)
    if (pq[0][0] - A) * count <= K: # 次の成長度に追いつけるなら追いつくまで配る
        K -= (pq[0][0] - A) * count
        next_a, next_count = heappop(pq)
        heappush(pq, (next_A, count + next_count))
    else:
        heappush(pq, (A + K // count + 1, K % count))
        heappush(pq, (A + K // count, count - K % count))

ans = 1
for A, count in pq:
    ans *= pow(A, count, 1000000007)
    ans %= 1000000007
print(ans)