Overview

This problem asks us to choose and harvest \(K\) trees out of \(N\) trees, whose deliciousness decreases each day, to maximize the total deliciousness obtained. By showing that the optimal order to harvest the chosen fruits is in “descending order of the decrease rate \(D_i\)”, we can sort the trees and apply dynamic programming (DP) to solve the problem in \(O(NK)\).

Analysis

1. Determining the Harvesting Order (Exchange Argument)

First, assume that the subset of trees to harvest has already been chosen. Now, let us consider in what order they should be harvested.

Consider two trees, \(i\) and \(j\), harvested on two consecutive days (day \(t\) and day \(t+1\)). - If tree \(i\) is harvested first (on day \(t\)) and tree \(j\) is harvested second (on day \(t+1\)), the total reduction in deliciousness is: \((t - 1) D_i + t D_j\) - Conversely, if tree \(j\) is harvested first and tree \(i\) is harvested second, the total reduction in deliciousness is: \((t - 1) D_j + t D_i\)

The condition for harvesting tree \(i\) first to be more advantageous (i.e., having a smaller reduction) is: \((t - 1) D_i + t D_j \leq (t - 1) D_j + t D_i \iff D_j \leq D_i \iff D_i \geq D_j\)

Intuitively, the larger the daily decrease of a fruit, the greater the loss if it is not harvested early. Therefore, regardless of which trees are chosen, it is always optimal to harvest the selected trees in descending order of \(D_i\).

2. Reduction to Dynamic Programming (DP)

Since we know the optimal harvesting order, we can sort all trees in advance in descending order of \(D_i\) (and in descending order of \(A_i\) if \(D_i\) is equal). Then, any chosen trees will always be harvested in the order of this sorted sequence (trees appearing earlier are harvested on earlier days).

This allows us to formulate a dynamic programming (DP) approach similar to the knapsack problem: “iterate through the trees in order from front to back, deciding whether or not to harvest each one.”

3. Handling Non-Positive Deliciousness

According to the problem statement, the deliciousness obtained is \(\max(0, A_i - (t - 1) D_i)\), which never drops below \(0\). Strictly speaking, we must harvest \(K\) trees; however, harvesting a tree whose deliciousness has dropped to \(0\) or below does not change the total sum (as it contributes \(0\) deliciousness). Therefore, we can reframe the problem as “choosing \(j\) trees (\(0 \leq j \leq K\)) that yield positive deliciousness,” and it suffices to find the maximum value among choosing any \(j \leq K\) trees.

Algorithm

1. Receive the information for each tree as a pair \((D_i, A_i)\), and sort them in descending order of \(D_i\).
2. Define the DP table:
   • dp[j]: The maximum total deliciousness obtained by choosing and harvesting \(j\) trees from those considered so far.
   • Initial values: dp[0] = 0, and all other entries are set to \(-1\) (representing unreachable states).
3. Iterate through each tree \((D, A)\) in the sorted order and update the DP table:
   • If this tree is chosen as the \(j\)-th tree, the deliciousness obtained is \(A - (j - 1) \times D\).
   • For all \(j\) where this value is positive (\(j \leq K\) and \(A - (j - 1)D > 0\)), update the table in descending order of \(j\): $\(\mathrm{dp}[j] = \max(\mathrm{dp}[j], \mathrm{dp}[j - 1] + (A - (j - 1) \times D))\)$
4. The final answer is \(\max_{0 \leq j \leq K} (\mathrm{dp}[j])\).

Complexity

• Time Complexity:
  • Sorting the trees: \(O(N \log N)\)
  • DP transitions: For \(N\) trees, each performs up to \(K\) transitions, taking \(O(NK)\)
  • Total time complexity is \(O(N \log N + NK)\), which comfortably runs within the time limit under the constraints \(N, K \leq 5000\).
• Space Complexity:
  • Storing the trees takes \(O(N)\) memory, and the DP table takes \(O(K)\) memory, for a total of \(O(N + K)\).

Implementation Notes

• Update Order of the DP Array: When updating the DP state using a 1D array, iterate through the loop for \(j\) from largest to smallest (in descending order) to avoid choosing the same tree multiple times.

• Pruning Unnecessary Computations: For \(j\) where \(A - (j - 1) \times D \leq 0\), choosing the tree does not increase the deliciousness (or would yield a negative value), so these transitions can be skipped. When \(D > 0\), the upper bound for \(j\) where deliciousness remains positive is \(j \leq \lfloor \frac{A - 1}{D} \rfloor + 1\). Skipping unnecessary loop iterations speeds up the execution.

  Source Code

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])

    trees = []
    idx = 2
    for _ in range(N):
        a = int(input_data[idx])
        d = int(input_data[idx + 1])
        trees.append((d, a))
        idx += 2

    # D の降順、タイブレークは A の降順でソート
    trees.sort(key=lambda x: (x[0], x[1]), reverse=True)

    dp = [-1] * (K + 1)
    dp[0] = 0

    max_j = 0
    for d, a in trees:
        if d == 0:
            limit_j = K
        else:
            limit_j = (a - 1) // d + 1
            if limit_j > K:
                limit_j = K

        curr_upper = max_j + 1
        if curr_upper > limit_j:
            curr_upper = limit_j

        for j in range(curr_upper, 0, -1):
            prev = dp[j - 1]
            if prev != -1:
                val = a - (j - 1) * d
                cand = prev + val
                if cand > dp[j]:
                    dp[j] = cand

        if max_j < curr_upper:
            max_j = curr_upper

    print(max(dp))


if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3.8-flash-high.