어? 금지

🤔 접근

이전에도 아주 비슷한 문제를 냅색 문제처럼 접근하였다가 시간초과가 났었는데 이번에도 같은 실수를 하였다.
t의 범위가 $(1 \leq t_i \leq 10^9\ ;\ t_{i-1} < t_i)$  이라는 것을 고려했다면 절대 max(t)를 가지고 냅색 문제처럼 풀지 않았을 것이다.

결론적으로 이 문제는, 알고리즘 스터디에서 많이 풀었던 #binary_search #dp 에 해당하는 문제였다. 이전에 벨로그에 기록해 둔 문제와도 아주 유사한 문제다.
비슷한 문제 : 전시장

💻 코드

# 30621
import sys
import bisect
input = sys.stdin.readline

n = int(input())
T = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

dp_t = [0]
dp_c = [0]
for i in range(n):
    t, b, c = T[i], B[i], C[i]
    past_t = t - b

    idx = bisect.bisect_left(dp_t, past_t) - 1
    if idx <= 0:
        value = max(c, dp_c[-1])
    else:
        value = max((dp_c[idx] + c), dp_c[-1])
    dp_t.append(t)
    dp_c.append(value)

print(dp_c[-1])