Submission #68182991

---

Source Code Expand

N = int(input())
P = []
A = []
B = []
    
for _ in range(N):
    p, a, b = map(int, input().split())
    P.append(p)
    A.append(a)
    B.append(b)

dp = [[0] * 1001 for _ in range(N+1)]
for t in range(1001):
    dp[-1][t] = t
    
for n in range(N-1, -1, -1):
    cdp = dp[n]
    ndp = dp[n+1]
    p, a, b = P[n], A[n], B[n]
    for t in range(1001):
        if p >= t:
            cdp[t] = ndp[t + a]
        else:
            cdp[t] = ndp[max(0, t - b)]

Bsum = [0]
for b in B:
    Bsum.append(Bsum[-1] + b)

from bisect import bisect_left


Q = int(input())
for _ in range(Q):
    X = int(input())
    if X > 1000:
        pos = bisect_left(Bsum, X-1000)
        if pos == len(Bsum):
            X -= Bsum[-1]
            print(X)
        else:
            X -= Bsum[pos]
            print(dp[pos][X])
    else:
        print(dp[0][X])

    

Submission Info

Judge Result