Overview

This problem is a variant of the knapsack problem where Takahashi selects products he can purchase before the department store’s closing time, maximizing the total bargain value.

Analysis

The time available for Takahashi to make purchases is \(T - S\) minutes, and each product requires \(C_i\) minutes to complete the purchase procedure — a product cannot be purchased unless the procedure is completed. A brute-force approach would try all \(2^N\) combinations, which is far too expensive when \(N \leq 100\). Therefore, we consider solving this efficiently using dynamic programming.

Algorithm

Similar to the classic knapsack problem, we use dynamic programming (DP). We define the DP table as dp[j] = the maximum bargain value when using up to j minutes of time. For each product, we decide whether to purchase it when \(j\) minutes are available. However, purchasing requires \(j \geq C_i\).

Specifically, for each product \((C_i, P_i)\), we decrease the available time \(j\) from \(T - S\) down to \(C_i\), updating with dp[j] = max(dp[j], dp[j - C_i] + P_i). By updating from the back (in decreasing order), we ensure that the same product is not selected more than once.

Complexity

• Time complexity: \(O(N \times (T - S))\)
• Space complexity: \(O(T - S)\)

Implementation Notes

1. Calculate the available time as available_time = T - S

2. Initialize the DP table with a size of available_time + 1

3. For each product, iterate over the time loop from back to front (to prevent duplicate selection of the same product)

4. If available_time is 0 or less (the store closes immediately upon arrival), output 0

   Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    S = int(data[2])
    items = []
    index = 3
    for i in range(n):
        c = int(data[index])
        p = int(data[index+1])
        index += 2
        items.append((c, p))
    
    available_time = T - S
    dp = [0] * (available_time + 1)
    
    for c, p in items:
        for j in range(available_time, c - 1, -1):
            if dp[j] < dp[j - c] + p:
                dp[j] = dp[j - c] + p
                
    print(max(dp) if available_time > 0 else 0)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.