Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
def knapsack_meetinthemiddle(n, cap, item):
    if n % 2 != 0: item.append((0, 0))
    m = (n + 1) // 2
    M = 2**m
    item1 = item[:m]
    item2 = item[m:]
    S1 = [None] * (M)
    S2 = [None] * (M)
    for i in range(M):
        sumv1, sumw1, sumv2, sumw2 = 0, 0, 0, 0
        for j in range(m):
            if (i >> j) & 1:
                v1, w1 = item1[j]
                v2, w2 = item2[j]
                sumv1 += v1
                sumw1 += w1
                sumv2 += v2
                sumw2 += w2
        S1[i] = (sumw1, sumv1)
        S2[i] = (sumw2, sumv2)
    S1.sort()
    S2.sort()
    res, j, tmp = 0, 0, 0
    for sw1, sv1 in S1[::-1]:
        if sw1 > cap: continue
        while j < M and sw1 + S2[j][0] <= cap:
            tmp = max(tmp, S2[j][1])
            j += 1
        res = max(res, sv1 + tmp)
    return res


N = int(input())

I = [tuple(map(int, input().split())) for _ in range(N)]

Q = int(input())

if N < 2**10:
    for _ in range(Q):
        u, L = map(int, input().split())
        item = []
        cnt = 0
        while u:
            item.append(I[u - 1])
            cnt += 1
            u //= 2
        print(knapsack_meetinthemiddle(cnt, L, item))

else:
    T = [[None] * (2**10) for _ in range(2**9)]
    for i in range(2**9, 2**10):
        for j in range(2**10):
            sumv, sumw = 0, 0
            for k in range(10):
                if (j >> k) & 1:
                    v, w = I[((i + 1) << k) - 1]
                    sumv += v
                    sumw += w
            T[i - 2**9][j] = (sumw, sumv)
        T[i - 2**9].sort()

    for _ in range(Q):

        u, L = map(int, input().split())
        if u < 2**10:
            item = []
            cnt = 0
            while u:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            print(knapsack_meetinthemiddle(cnt, L, item))
        else:
            item = []
            cnt = 0
            while u >= 2**10:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            S = [None] * (2**cnt)
            for j in range(2**cnt):
                sumv, sumj = 0, 0
                for k in range(cnt):
                    if (j >> k) & 1:
                        v, w = item[k]
                        sumv += v
                        sumw += w
                S[j] = (sumw, sumv)
            S.sort()
            #T[u - 2**8]
            res, j, tmp = 0, 0, 0
            for sw, sv in S[::-1]:
                if sw > L: continue
                while j < 2**10 and sw + T[u - 2**9][j][0] <= L:
                    tmp = max(tmp, T[u - 2**9][j][1])
                    j += 1
                res = max(res, sv + tmp)
            print(res)

Submission status: Runtime Error

Solution code:
def main():
    M = 2**9
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    def cal(n,l):
        if n < M:
            return dp[n][l]
        else:
            res = 0
            v = []
            while n >= M:
                v.append(n)
                n //= 2
            m = len(v)
            v_tot = 0
            w_tot = 0
            for n in range(2**m):
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[v[k]-1]
                        w_tot += W[v[k]-1]
                if w_tot <= W:
                    res = max(res,v_tot+dp[v[-1]//2][W-w_tot])
            return res

    Q = int(input())
    vL = [list(map(int,input().split())) for _ in range(Q)]

    for i in range(Q):
        v,L = vL[i]
        print(cal(v,L))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    B = [[int(v) for v in input().split()] for _ in range(N)]
    WV = [[] for _ in range(N)]
    Lim = pow(2, 10)
    WV[0].append((0, 0))
    WV[0].append((B[0][1], B[0][0]))
    for i in range(1, min(N, Lim)):
        s = set()
        for w, v in WV[i//2]:
            s |= {(w, v)}
            if w + B[i][1] <= 10 ** 5: s |= {(w + B[i][1], v + B[i][0])}
        WV[i] = sorted(s)
        for j in range(1, len(WV[i])):
            if WV[i][j-1][1] > WV[i][j][1]: WV[i][j] = (WV[i][j][0], WV[i][j-1][1])
    #print(WV)

    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        add = set()
        add |= {(0, 0)}
        while v >= Lim:
            s = set()
            for w, v in add:
                if w + B[v-1][1] <= L:
                    s |= {(w+B[v-1][1], v + B[v-1][0])}
            add |= s
            v //= 2
        ans = 0
        le = len(WV[v-1])
        for w, val in add:
            low, high = 0, le
            #print(WV[v-1], low, high, le, v-1)
            while high - low > 1:
                mid = (high + low) // 2
                if WV[v-1][mid][0] + w > L: high = mid
                else: low = mid
            ans = max(ans, val + WV[v-1][low][1])
        Ans[q] = ans

    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def main():
    M = 2**9
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    def cal(n,l):
        if n < M:
            return dp[n][l]
        else:
            res = 0
            v = []
            while n >= M:
                v.append(n)
                n //= 2
            m = len(v)
            v_tot = 0
            w_tot = 0
            for n in range(2**m):
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[v[k]]
                        w_tot += W[v[k]]
                if w_tot <= W:
                    res = max(res,v_tot+dp[v[-1]//2][W-w_tot])
            return res

    Q = int(input())
    vL = [list(map(int,input().split())) for _ in range(Q)]

    for i in range(Q):
        v,L = vL[i]
        print(cal(v,L))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    M = 2**9
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    def cal(n,l):
        if n < M:
            return dp[n][l]
        else:
            res = 0
            v = []
            while n >= M:
                v.append(n)
                n //= 2
            m = len(v)
            v_tot = 0
            w_tot = 0
            for n in range(2**m):
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[v[k]]
                        w_tot += W[v[k]]
                if w_tot <= W:
                    res = max(res,v_tot+dp[v[-1]//2][W-w_tot])
            return res

    Q = int(input())
    vL = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
    v,L = vL[i]
    print(cal(v,L))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
M = 2**10
N = int(input())
V = []
W = []
for i in range(N):
    v,w = map(int,input().split())
    V.append(v)
    W.append(w)

dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

for n in range(1,min(M,N+1)):
    for l in range(10**5+1):
        c = 0
        if l>=W[n-1]:
            c = dp[n//2][l-W[n-1]]+V[n-1]
        dp[n][l] = max(dp[n//2][l],c)
for n in range(min(M,N+1)):
    for l in range(1,10**5+1):
        dp[n][l] = max(dp[n][l],dp[n][l-1])

def cal(n,l):
    if n < M:
        return dp[n][l]
    elif (n,l) in memo:
        return memo[(n,l)]
    else:
        res = 0
        v = []
        while n >= M:
            v.append(n)
            n //= 2
        m = len(v)
        v_tot = 0
        w_tot = 0
        for n in range(2**m):
            for k in range(m):
                if 2**k&n==2**k:
                    v_tot += V[v[k]]
                    w_tot += W[v[k]]
            if w_tot <= W:
                res = max(res,v_tot+dp[v[-1]//2][W-w_tot])
        return res

Q = int(input())
vL = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
    v,L = vL[i]
    print(cal(v,L))

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def make(A, v):
    T = []
    while v != 0:
        T.append(A[v - 1])
        v //= 2

    M = len(T)
    K = []
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]
            if W > 10 ** 5 + 10:
                break
        
        if W < 10 ** 5 + 10:
            K.append((W, V))
    
    K.sort(key=lambda l: (l[0], -l[1]))

    W2 = [0]
    V2 = [0]
    mv = 0
    for w, v in K:
        if v <= mv:
            continue

        mv = v
        W2.append(w)
        V2.append(mv)

    return (tuple(W2), tuple(V2))

@lru_cache(maxsize=None)
def f(A, v, L):
    T = []
    while v != 0:
        T.append(A[v - 1])
        v //= 2

    M = len(T)
    res = 0
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]

        if W <= L:
            res = max(res, V)

    return res


P = 8
@lru_cache(maxsize=None)
def f2(A, v, L, V2, W2):
    T = []
    while v >= 2 ** P:
        T.append(A[v - 1])
        v = v >> 1

    M = len(T)
    res = 0
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]
            if W > L:
                break

        R = L - W
        t = bisect.bisect_right(W2, R)
        res = max(res, V + V2[min(t, len(W2)) - 1])

    return res


def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(tuple(read_values()))
    A = tuple(A)
    K = dict()
    Q = int(input())
    ans = [""] * Q
    for q in range(Q):
        v, L = read_values()
        if v.bit_length() <= P:
            ans[q] = str(f(A, v, L))
        else:
            b = v.bit_length()
            v2 = v >> (b - P)
            K2 = K.setdefault(v2, make(A, v2))
            ans[q] = str(f2(A, v, L, K2))

    print("\n".join(ans))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

# for _ in range(k):
#     next_a = [0] * n
#     for i, brightness in enumerate(a):
#         begin = max(0, i - brightness)
#         end = min(i + brightness + 1, n)
#         for j in range(begin, end):
#             next_a[j] += 1
#     print(next_a)
#     a = next_a.copy()
print(a)
for t in range(k):
    print(t)
    finish = True
    stack = []
    for i, brightness in enumerate(a):
        if brightness != n:
            finish = False
        begin = i - brightness - 0.5
        end = i + brightness + 0.5
        stack.append((begin, "IN"))
        stack.append((end, "OUT"))
    if finish:
        break
    stack.sort(key=lambda x: x[0])
    now = 0
    pos = 0
    for inout in stack:
        if pos > n-1:
            break
        while pos < inout[0]:
            if pos > n-1:
                break
            a[pos] = now
            pos += 1
        if inout[1] == "IN":
            now += 1
        elif inout[1] == "OUT":
            now -= 1
print(*a, sep=" ")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
import numpy as np
def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs=[]
    ws=[]
    costs=tuple(tuple(map(int, input().split())) for i in range(N))
    visited=[0]*N
    Q=int(input())
    qs= tuple(tuple(map(int, input().split())) for i in range(Q))
    maxL=int(max([qs[i][1] for i in range(Q)]))

    dps=dict()
    dp=np.zeros(maxL+1,dtype='i8')
    v,w=costs[0]

    #print(dp[w:maxL+1])
    if w<=maxL:
        #print(w,maxL+1,maxL+1-w)        
        dp[w:maxL+1]=np.maximum(dp[0:maxL+1-w]+v,dp[w:maxL+1])

    dps[1]=dp
    visited[0]=1
    #@lru_cache(maxsize = None)
    #import numba
    #@numba.jit(nopython=True)
    def r(n,dpo):
        dp=np.copy(dpo)
        v,w=costs[n-1]
        #if n==4:
            #print(par)
            #print(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        if w<=maxL:
            dp[w:maxL+1]=np.maximum(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        dps[n]=dp
        return dp
        
    for v,L in qs:
        q=deque()
        while v:
            if v in dps:
                dp=dps[v]
                break
            else:
                q.append(v)
                v=v//2
        #print(dp)
        while q:
            v=q.pop()
            dp=r(v,dp)

            
            

        print(dp[L])
        #print(dp)
    
    #print(dps[8])
        
        


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heappush

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    bag = [tuple(nm()) for _ in range(n)]
    q = ni()
    query = [tuple(nm()) for _ in range(q)]
    ansd = dict()
    g = [None]* 2 ** 10

    def calc(v):
        W = 10**5 + 1
        res = [0] * W
        l = list()
        while v:
            l.append(bag[v-1])
            v >>= 1
        m = len(l)
        for bit in range(1 << m):
            cv = cw = 0
            for i in range(m):
                if bit & (1 << i):
                    cv += l[i][0]
                    cw += l[i][1]
                    if cw > W:
                        break
            else:
                if res[cw] < cv:
                    res[cw] = cv
        for i in range(W-1):
            if res[i+1] < res[i]:
                res[i+1] < res[i]
        return res


    for _v, L in query:
        v = _v
        if v < 2 ** 10:
            l = list()
            while v:
                l.append(bag[v-1])
                v >>= 1
            m = len(l)
            ans = 0
            for bit in range(1 << m):
                cv = cw = 0
                for i in range(m):
                    if bit & (1 << i):
                        cv += l[i][0]
                        cw += l[i][1]
                        if cw > L:
                            break
                else:
                    if cv > ans:
                        ans = cv

            ansd[(_v, L)] = ans

        else:
            l = list()
            while v >= 2 ** 10:
                l.append(bag[v-1])
                v >>= 1
            if g[v] is None:
                g[v] = calc(v)
            m = len(l)
            ans = 0
            for bit in range(1 << m):
                cv = cw = 0
                for i in range(m):
                    if bit & (1 << i):
                        cv += l[i][0]
                        cw += l[i][1]
                        if cw > L:
                            break
                else:
                    if cv + g[v][L-cw] > ans:
                        ans = cv + g[v][L-cw]
            ansd[(_v, L)] = ans

    for c in query:
        print(ansd[c])
    return

solve()

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, ceil
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
#def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
VW = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
vL = [list(map(int, input().split())) for _ in range(Q)]
depth = ceil(math.log(N, 2))
# print('depth', depth)
sumW = 0
for vw in VW:
    v, w = vw
    sumW += w

dp = [[0]*(sumW+100) for i in range(2**depth)]

for w in range(sumW):
    v1, w1 = VW[0]
    if w1<=w:
        dp[1][w] = v1
    
# pl(dp)

for i in range(1, 2**(depth-1)):
    # print('i', i)
    # print('left')
    v, w = VW[2*i-1]
    for k in range(sumW):
        # print('k', k)
        dp[2*i][k] = max(dp[i][k-w]+v, dp[i][k])

    # print('right')
    v, w = VW[2*i]
    for k in range(sumW):
        dp[2*i+1][k] = max(dp[i][k-w]+v, dp[i][k])
# pl(dp)
for vl in vL:
    v, L = vl
    print(dp[v][L])

Submission status: Runtime Error

Solution code:
def main():
    import bisect
    import collections
    import sys
    N = int(input())
    VW = [tuple(map(int, input().split())) for i in range(N)]
    input = sys.stdin.buffer.readline
    Q = int(input())

    prev = [0]
    dp = [[]]*(N+1)
    dp[0] = [(0, 0)]
    d = collections.defaultdict(list)
    for i in range(Q):
        v, L = map(int, input().split())
        d[v].append((L, i))

    ans = [0]*Q

    for i in range(1, N+1):
        dp[i] = list(dp[i//2])
        for x, y in dp[i//2]:
            dp[i].append((x + VW[i-1][0], y+VW[i-1][1]))
        dp[i].sort(key=lambda x: (x[1], x[0]))
        tmp = [x[1] for x in dp[i]]
        for x in d[i]:

            id = bisect.bisect_right(tmp, x[0])
            ans[x[1]] = dp[i][id-1][0]

    print(*ans, sep="\n")


main()

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, ceil
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
VW = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
vL = [list(map(int, input().split())) for _ in range(Q)]
depth = ceil(math.log(N, 2))
# print('depth', depth)
sumW = 0
for vw in VW:
    v, w = vw
    sumW += w

dp = [[0]*(sumW+100) for i in range(2**depth)]

for w in range(sumW):
    v1, w1 = VW[0]
    if w1<=w:
        dp[1][w] = v1
    
# pl(dp)

for i in range(1, 2**(depth-1)):
    # print('i', i)
    # print('left')
    v, w = VW[2*i-1]
    for k in range(sumW):
        # print('k', k)
        dp[2*i][k] = max(dp[i][k-w]+v, dp[i][k])

    # print('right')
    v, w = VW[2*i]
    for k in range(sumW):
        dp[2*i+1][k] = max(dp[i][k-w]+v, dp[i][k])
# pl(dp)
for vl in vL:
    v, L = vl
    print(dp[v][L])

Submission status: Runtime Error

Solution code:
import bisect
import collections
import sys
N = int(input())
VW = [tuple(map(int, input().split())) for i in range(N)]
input = sys.stdin.buffer.readline
Q = int(input())

prev = [0]
dp = [[]]*(N+1)
dp[0] = [(0, 0)]
d = collections.defaultdict(list)
for i in range(Q):
    v, L = map(int, input().split())
    d[v].append((L, i))

ans = [0]*Q

for i in range(1, N+1):
    dp[i] = list(dp[i//2])
    for x, y in dp[i//2]:
        dp[i].append((x + VW[i-1][0], y+VW[i-1][1]))
    dp[i].sort(key=lambda x: (x[1], x[0]))
    tmp = [x[1] for x in dp[i]]
    for x in d[i]:

        id = bisect.bisect_right(tmp, x[0])
        ans[x[1]] = dp[i][id-1][0]

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
VW = [lr() for _ in range(N)]
answer = [None] * (N+1)
dp = np.array([0] * (10 ** 5 + 1), dtype=np.int64)

def dfs(dp, i):
    v, w = VW[i-1]
    next = dp.copy()
    next[w:] = np.maximum(dp[w:], dp[:-w] + v)
    answer[i] = next
    if 2 * i <= N:
        dfs(next, 2*i)
    if 2 * i + 1 <= N:
        dfs(next, 2*i+1)

dfs(dp, 1)
Q = ir()
Z = []
for _ in range(Q):
    v, L = lr()
    Z.append(answer[v][L])

print('\n'.join(map(str, Z)))

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, log2, ceil
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
VW = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
vL = [list(map(int, input().split())) for _ in range(Q)]
depth = ceil(log2(N))
# print('depth', depth)
sumW = 0
for vw in VW:
    v, w = vw
    sumW += w

dp = [[0]*(sumW+100) for i in range(2**depth)]

for w in range(sumW):
    v1, w1 = VW[0]
    if w1<=w:
        dp[1][w] = v1
    
# pl(dp)

for i in range(1, 2**(depth-1)):
    # print('i', i)
    # print('left')
    v, w = VW[2*i-1]
    for k in range(sumW):
        # print('k', k)
        dp[2*i][k] = max(dp[i][k-w]+v, dp[i][k])

    # print('right')
    v, w = VW[2*i]
    for k in range(sumW):
        dp[2*i+1][k] = max(dp[i][k-w]+v, dp[i][k])
# pl(dp)
for vl in vL:
    v, L = vl
    print(dp[v][L])

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
import itertools
for i in range(N):
  if (i+1)//2 == 0:
    V, W = map(int, input().split())
    A.append([V, W])
  else:
    a = A[(i+1)//2-1]
    V, W = map(int, input().split())
    a.append([V, W])
    A.append(a)
Q = int(input())
for i in range(Q):
  v, L = map(int, input().split())
  n = len(A[v-1])
  B = list(itertools.product([0, 1], repeat=n))
  S = []
  for b in B:
    s = 0
    w = 0
    for j in range(n):
      s += A[v-1][j][2]*b[j]
      w += A[v-1][j][1]*b[j]
    if s >= L:
      S.append(w)
  S.sort()
  if len(S) == 0:
    ans = 0
  elif len(S) == 1:
    ans = S[0]
  else:
    ans = S[-1]
  print(ans)