Overview

This is a problem where you harvest fruits from \(N\) orchards over \(K\) days, maximizing the total harvest. Since each orchard has a daily harvest limit, you need to optimally decide which orchards to choose, in what order, and how many times.

Analysis

Understanding the harvest structure of each orchard

Orchard \(i\) has \(A_i\) fruits, and you can harvest at most \(B_i\) per day. If you repeatedly choose this orchard, the harvest amounts are as follows:

Example: When \(A_i = 13, B_i = 5\) - 1st time: \(\min(13, 5) = 5\) fruits harvested (8 remaining) - 2nd time: \(\min(8, 5) = 5\) fruits harvested (3 remaining) - 3rd time: \(\min(3, 5) = 3\) fruits harvested (0 remaining)

In other words, from orchard \(i\), you can harvest \(B_i\) fruits \(\lfloor A_i / B_i \rfloor\) times, and the remainder \(A_i \bmod B_i\) fruits once (if the remainder is non-zero).

Thinking in terms of “harvest slots”

We can decompose each orchard’s harvest into independent slots. Orchard \(i\) generates the following set of slots: - \(\lfloor A_i / B_i \rfloor\) slots of value \(B_i\) - 1 slot of value \(A_i \bmod B_i\) (if non-zero)

Combining slots from all orchards, each slot represents “the harvest obtained by spending one day.” To maximize the harvest over \(K\) days, we simply select the \(K\) slots with the largest values from all slots.

Problems with the naive approach

The total number of slots can be up to \(\sum (A_i / B_i + 1)\), which can reach \(10^9\) when \(A_i\) is \(10^9\) and \(B_i\) is \(1\). Enumerating and sorting all slots is infeasible.

Solving with binary search

“The number of slots with value \(\geq t\)” is monotonically decreasing with respect to \(t\). So we binary search on \(t\) to find the maximum \(t\) such that “the number of slots with value \(\geq t\) is at least \(K\).”

When \(t\) is fixed, the slots with value \(\geq t\) for orchard \(i\) are: - When \(B_i \geq t\): \(\lfloor A_i / B_i \rfloor\) slots of value \(B_i\) (all \(\geq t\)), plus 1 more if the remainder \(A_i \bmod B_i \geq t\) - When \(B_i < t\): 0 slots

This allows us to compute the count and total value in \(O(N)\).

Computing the final answer

For the threshold \(t\) found by binary search, let \(\text{cnt}\) be the number of slots with value \(\geq t\) and \(s\) be their total sum. Since \(\text{cnt} \geq K\), we need to remove the excess \(\text{cnt} - K\) slots. The ones to remove are slots with value exactly \(t\) (the smallest ones), so:

\[\text{ans} = s - (\text{cnt} - K) \times t\]

Algorithm

1. Read each orchard \((A_i, B_i)\).
2. Use binary search to find the maximum \(t\) such that the number of slots with value \(\geq t\) is at least \(K\).
3. For that \(t\), compute the slot count \(\text{cnt}\) and total value \(s\).
4. If \(t = 0\), all fruits can be harvested (\(K\) is sufficiently large), so output \(\sum A_i\).
5. Otherwise, output \(s - (\text{cnt} - K) \times t\).

Complexity

• Time complexity: \(O(N \log(\max B_i))\) (binary search runs \(O(\log(\max B_i))\) times, each taking \(O(N)\))
• Space complexity: \(O(N)\)

Implementation Notes

• The binary search range is \([0, 10^9 + 1]\), and the case \(t = 0\) (when all slots are exhausted but still fewer than \(K\) days) is handled specially.

• Since \(K\) can be as large as \(10^{18}\), enumerating all slots is impossible. The essence is to reduce the problem to an \(O(N)\) evaluation function via binary search.

• In the count_and_sum function, orchards with \(B_i < t\) have no slots with value \(\geq t\), so they can be skipped immediately.

  Source Code

import sys
from sys import stdin

def solve():
    input_data = stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    A = []
    B = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        A.append(a)
        B.append(b)
    
    def count_and_sum(t):
        # Count slots with value >= t, and their total sum
        cnt = 0
        s = 0
        for i in range(N):
            if B[i] >= t:
                f = A[i] // B[i]
                p = A[i] % B[i]
                cnt += f
                s += f * B[i]
                if p >= t:
                    cnt += 1
                    s += p
        return cnt, s
    
    # Binary search for largest t where count >= K
    lo, hi = 0, 10**9 + 1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        cnt, _ = count_and_sum(mid)
        if cnt >= K:
            lo = mid
        else:
            hi = mid - 1
    
    t = lo
    if t == 0:
        # All fruits can be harvested
        print(sum(A))
        return
    
    cnt, s = count_and_sum(t)
    # We have cnt slots with value >= t, summing to s
    # We only need K of them; drop (cnt - K) slots of value exactly t
    ans = s - (cnt - K) * t
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.