Python题解

import bisect 
 
n, t = map(int, input().split()) 
a = list(map(int, input().split())) 
v_total = 0 
options = [] 
 
for i in range(n): 
    cost_i, v_i = map(int, input().split()) 
    v_total += v_i 
    end_i = a[i] + t - 1 
    s_i = v_i - cost_i 
    if s_i > 0: 
        options.append((end_i,  s_i)) 
options.sort()  
m = len(options) 
if m == 0: 
    print(v_total) 
else: 
    end_list = [x[0] for x in options] 
    dp = [0] * m 
    dp[0] = options[0][1] 
    for i in range(1, m): 
        current_end, current_s = options[i] 
        target = current_end - t 
        j = bisect.bisect_right(end_list,  target, 0, i) - 1 
        if j >= 0: 
            candidate = dp[j] + current_s 
        else: 
            candidate = current_s 
        dp[i] = max(dp[i-1], candidate) 
    max_save = dp[-1] 
    print(v_total - max_save)