Overview

Treat each request as an item with “weight \(W_i\) and net profit \(V_i=P_i-C_i\)”, determine whether it is possible to achieve a total net profit of at least \(T\) with total weight at most \(S\), and if so, minimize the number of items selected.

Analysis

• The conditions require “achieving at least a certain profit under a weight constraint” as well as “minimizing the number of items selected.”
  A simple 0/1 knapsack (maximizing profit within weight) alone cannot track how many items were selected, so we cannot determine the minimum count.
• If we try to directly DP for “the minimum number of items to achieve profit \(\ge T\)”:
  • The total profit can reach up to \(50 \times 10^4 = 5\times 10^5\), making a DP along the profit axis potentially heavy.
  • Furthermore, \(V_i\) can be negative, which makes a profit-axis DP difficult to handle (e.g., negative indices).
• The key observation here is that \(N \le 50\) is small.
  Since the number of items selected is at most 50, it is effective to include the count as a dimension of the DP.

Algorithm

Consider the following DP:

• \(dp[k][w] =\) “the maximum net profit achievable when selecting exactly \(k\) items with total weight \(w\)”
• Initialization:
  • Selecting nothing with weight 0 gives profit 0: \(dp[0][0]=0\)
  • Everything else is impossible, so set to \(-\infty\) (in code, a large negative number NEG)

For each request (net profit \(v\), weight \(w\)), since we select it 0 or 1 times, the transition is as follows:

• If \(dp[k][cw]\) is reachable, then by adding this request:
  • Count: \(k \to k+1\)
  • Weight: \(cw \to cw+w\) (provided \(cw+w \le S\))
  • Profit: \(dp[k][cw] + v\) and update accordingly.

Similar to the standard 0/1 knapsack, to avoid using the same request multiple times: - Iterate over count \(k\) in descending order - Iterate over weight \(cw\) in descending order as well

Finally, check \(k=1,2,\dots,N\) in ascending order: - If \(\max_{0\le w\le S} dp[k][w] \ge T\) output the smallest such \(k\) as the answer. If no such \(k\) exists, output -1.

Complexity

• Time complexity: \(O(N^2 S)\)
  (For each request, we iterate over \(k=0..N\) and weight \(0..S\). Under the constraints, this is at most approximately \(50^2 \times 10^4 = 2.5\times 10^7\).)
• Space complexity: \(O(NS)\)
  (The \(dp\) array is \((N+1)\times(S+1)\).)

Implementation Notes

• Fill unreachable states with NEG (a sufficiently small value) and skip transitions from states where the value is NEG.

• To maintain the 0/1 condition, the update loops must iterate in descending order for both count and weight (iterating in ascending order risks using the same request multiple times within the same loop).

• Items with \(W_i > S\) cannot be loaded anyway, so they can be skipped.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    S = next(it)
    T = next(it)

    items = []
    for _ in range(N):
        p = next(it)
        c = next(it)
        w = next(it)
        items.append((p - c, w))

    NEG = -10**18
    dp = [[NEG] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for v, w in items:
        if w > S:
            continue
        for k in range(N - 1, -1, -1):
            prev = dp[k]
            nxt = dp[k + 1]
            limit = S - w
            for cw in range(limit, -1, -1):
                pv = prev[cw]
                if pv == NEG:
                    continue
                nw = cw + w
                nv = pv + v
                if nv > nxt[nw]:
                    nxt[nw] = nv

    ans = -1
    for k in range(1, N + 1):
        if max(dp[k]) >= T:
            ans = k
            break
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.