Overview

This is a problem where you choose one of \(N\) orchards each day over \(K\) days to harvest from, maximizing the total harvest. At each orchard \(i\), you can harvest up to \(B_i\) fruits per day, and if fewer than \(B_i\) remain, you harvest all the remaining fruits.

Analysis

Decomposing Harvest Patterns

Focusing on a particular orchard \(i\) (with \(A_i\) fruits and a daily limit of \(B_i\)), if you keep choosing that orchard every day, the harvest proceeds as follows: - \(B_i\) fruits for \(d = \lfloor A_i / B_i \rfloor\) times (\(d\) days) - The remainder \(r = A_i \bmod B_i\) fruits for \(1\) time (\(1\) day) - After that, \(0\) fruits

For example, if \(A_i = 25, B_i = 10\), the harvest changes as \(10, 10, 5, 0, 0, \dots\).

Applying a Greedy Approach

Takahashi works for a total of \(K\) days. To maximize the total harvest, we should prioritize choosing “the orchard that yields the most fruits on that day” (greedy approach).

This is because even if you choose a harvest of \(Y < X\) on a given day when \(X\) is available, the opportunity to choose \(X\) simply remains for later. Since the total number of days is limited, it is optimal to select the \(K\) largest values in descending order (for \(K\) days).

Efficient Computation

Since \(K\) can be as large as \(10^{18}\), simulating day by day is infeasible. However, by decomposing the harvest from each orchard into pairs of (harvest amount, number of days that harvest is possible), the total number of data items is at most \(2N\). By sorting these in descending order of harvest amount and processing them in bulk, we can compute the answer efficiently.

Algorithm

1. For each orchard \(i=1 \dots N\), create the following “harvest items”:
   • \(A_i // B_i\) days with a harvest of \(B_i\)
   • \(1\) day with a harvest of \(A_i \% B_i\) (only if the remainder is non-zero)
2. Sort all created items in descending order of harvest amount (fruits per day).
3. While managing the remaining work days \(K\), iterate through the sorted items:
   • If the item’s “number of days” is at most \(K\), add the entire contribution to the total harvest and subtract the number of days from \(K\).
   • If the item’s “number of days” exceeds \(K\), harvest for only \(K\) days and stop.
4. Output the final total harvest.

Complexity

• Time complexity: \(O(N \log N)\)
  • Creating at most 2 items per orchard takes \(O(N)\).
  • Sorting the items takes \(O(N \log N)\).
  • Scanning through the items takes \(O(N)\).
• Space complexity: \(O(N)\)
  • The list storing the items uses \(O(N)\) memory.

Implementation Notes

• Handling large \(K\): Since \(K\) can reach \(10^{18}\), instead of looping, you need to compute how many days to work on the current item as min(count, days_left) and add the contribution all at once.

• Handling remainders: If \(A_i\) is divisible by \(B_i\), there is no need to add an item with remainder \(0\) (since it contributes nothing to the harvest).

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 果樹園の数, K: 作業日数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各果樹園について、1日あたりの収穫量とその収穫が可能な日数を計算する
    # 果樹園iでは、B_i 個を A_i // B_i 回収穫でき、
    # その後、余りの A_i % B_i 個を 1 回収穫できる
    items = []
    for i in range(N):
        A = int(input_data[2 + 2 * i])
        B = int(input_data[3 + 2 * i])
        
        d = A // B
        r = A % B
        
        if d > 0:
            items.append((B, d))
        if r > 0:
            items.append((r, 1))
            
    # 1日あたりの収穫量(value)が大きい順にソートする（貪欲法）
    items.sort(key=lambda x: x[0], reverse=True)
    
    total_harvest = 0
    days_left = K
    
    # 収穫量が多いものから順に、可能な限り日数(K)を割り当てる
    for value, count in items:
        if days_left <= 0:
            break
        
        # 現在の収穫量で作業する日数を決定
        take_days = count if count < days_left else days_left
        total_harvest += take_days * value
        days_left -= take_days
        
    # 合計収穫量を出力
    print(total_harvest)

if __name__ == '__main__':
    solve()

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