Overview

This problem asks us to choose \(K\) trees out of \(N\), assign each chosen tree to one of days \(1\) through \(K\) (one tree per day), and maximize the sum of \(\max(0, A_i-(t-1)D_i)\). By noticing the rearrangement property that “trees with larger \(D\) should be harvested earlier,” we can solve this with an \(O(NK)\) DP.

Analysis

Why Naive Approaches Fail

Just choosing which \(K\) trees to pick has \(\binom{N}{K}\) combinations, and assigning each tree to a specific day leads to a combinatorial explosion. While this is an “assignment problem” that could theoretically be solved using min-cost flow or the Hungarian algorithm, it would not run within the time limit for \(N=5000\).

Moreover, a simple greedy approach (picking the fruit with the maximum current value each day) also fails. For example:

• Tree 1: \(A=10,\ D=0\)
• Tree 2: \(A=11,\ D=100\)

With \(K=2\), if we pick Tree 1 on day \(1\) (value \(10\)), Tree 2 will yield \(\max(0,11-100)=0\) on day \(2\), for a total of \(10\). The optimal solution is to pick Tree 2 on day \(1\) (\(11\)) and Tree 1 on day \(2\) (\(10\)), giving a total of \(21\).

Key Observation: Harvesting in Descending Order of \(D\)

Claim: There exists an optimal solution where the fruits that actually yield a positive deliciousness are harvested in descending order of \(D\) (i.e., larger \(D\) on earlier days).

Proof (Exchange Argument): Suppose that in an optimal solution, tree \(u\) is harvested on day \(t\) and tree \(v\) is harvested on day \(t'\) (\(t<t'\)), both yield positive values, and \(D_u < D_v\). Let \(s=t'-t\). If we swap the days of \(u\) and \(v\):

• \(v\) is harvested \(s\) days earlier: Since its value was positive on day \(t'\), it is strictly positive on day \(t\) as well, so its value increases by exactly \(s\cdot D_v\).
• \(u\) is harvested \(s\) days later: Its value decreases by at most \(s\cdot D_u\) (since it is capped below at \(0\), the decrease cannot exceed this amount).

Thus, the total value increases by at least \(s(D_v-D_u)>0\), which contradicts the optimality of the solution. Therefore, in an optimal solution, harvests that yield a positive value are arranged in descending order of \(D\).

Handling Days with Value \(0\)

Trees that yield a value of \(0\) give \(0\) regardless of which tree is assigned, so such days can be treated as “empty” in the DP. Since \(N \ge K\), we can always assign any remaining unharvested tree to each empty day, and since its value is at least \(0\), we lose nothing (and conversely, the value calculated by the DP is always achievable).

Therefore, the problem can be rephrased as follows:

Sort the trees in descending order of \(D\). Maintaining this order, select a subset of trees and assign them to strictly increasing days \(t_1<t_2<\cdots\) (\(t_i \le K\)) in that order, maximizing the sum of their (positive) values.

This can be solved with an LCS-style (subsequence matching) DP.

Algorithm

1. Sort all trees in descending order of \(D\).
2. Define \(dp[i][j]\) as the maximum total value after considering the first \(i\) trees and using up days \(1\) through \(j\) (some days may be left empty).

There are 3 transitions: - Do not use tree \(i\): \(dp[i-1][j]\) - Leave day \(j\) empty: \(dp[i][j-1]\) - Harvest tree \(i\) on day \(j\): \(dp[i-1][j-1] + \max(0,\ A_i-(j-1)D_i)\)

$\(dp[i][j]=\max\bigl(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]+\max(0,A_i-(j-1)D_i)\bigr)\)\( 3. The answer is \)dp[N][K]$.

The \(i\) dimension can be optimized into a 1D array (by iterating \(j\) in ascending order and maintaining both the pre-update \(dp[j-1]\) (\(=dp[i-1][j-1]\)) and post-update \(dp[j-1]\) (\(=dp[i][j-1]\)) in variables).

Pruning

The last day on which tree \(i\) has a positive value is: $\(jm_i=\min\left(K,\ \left\lfloor\frac{A_i-1}{D_i}\right\rfloor+1\right)\quad (\text{if } D_i=0 \text{, then } jm_i=K)\)\( For \)j>jm_i\(, the added value becomes \)0\(, so the transition reduces to \)dp[j]\leftarrow\max(dp[j],dp[j-1])\(. Since \)dp\( is monotonically non-decreasing with respect to \)j$, once no updates occur, no further updates will happen thereafter, so we can break early. This significantly reduces the actual running time.

Complexity

• Time Complexity: \(O(N\log N + NK)\) (Sorting + DP. With pruning, it is practically around \(\sum_i \min(K, A_i/D_i+1)\))
• Space Complexity: \(O(N+K)\)

Implementation Notes

• Sort order: Descending order of \(D\). The order of trees with equal \(D\) does not affect the result (in code, sorting by (D, A) in descending order works).
• Update order for 1D DP: Iterate \(j=1,2,\dots\) in ascending order while keeping:
  • prev as the “pre-update \(dp[j-1]\)” (\(=dp[i-1][j-1]\))
  • newprev as the “post-update \(dp[j-1]\)” (\(=dp[i][j-1]\))

and update \(dp[j]=\max(dp[j],\ prev+v_j,\ newprev)\). Confusing these can lead to bugs where the same tree is harvested on multiple days or empty days cannot be formed. - Value calculation: Computing \(v_j=A_i-(j-1)D_i\) by updating iteratively with v -= d is faster. Within the range \(j\le jm_i\), \(v_j>0\) is guaranteed, so max(0,·) is unnecessary. - Overflow: The maximum possible answer is around \(5000\times10^9=5\times10^{12}\). This is not an issue in Python, but in languages like C++, be sure to use long long. - Case where \(D_i=0\): Since the value remains \(A_i\) regardless of the day it is harvested, set \(jm_i=K\) (beware of division by zero).

Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    trees = []
    idx = 2
    ap = trees.append
    for _ in range(n):
        a = int(data[idx]); d = int(data[idx+1])
        idx += 2
        ap((d, a))
    trees.sort(reverse=True)  # D descending

    dp = [0] * (k + 1)

    for d, a in trees:
        if d == 0:
            jm = k
        else:
            jm = (a - 1) // d + 1
            if jm > k:
                jm = k
        prev = 0          # old dp[j-1]
        newprev = 0       # new dp[j-1]
        v = a             # value at day j (j starts at 1): a - (j-1)*d
        j = 1
        while j <= jm:
            cur = dp[j]
            c = prev + v
            if c < cur:
                c = cur
            if c < newprev:
                c = newprev
            dp[j] = c
            newprev = c
            prev = cur
            v -= d
            j += 1
        # remaining days: value contribution is 0, just propagate carry
        while j <= k:
            if dp[j] < newprev:
                dp[j] = newprev
                j += 1
            else:
                break

    sys.stdout.write(str(dp[k]) + "\n")

main()

---

This editorial was generated by claude5opus-high.