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: Time Limit Exceeded

Solution code:
import sys
MX = 10**5
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(MX + 1):
            t = dpip[j]
            if j >= w:
                t = max(t, dpip[j - w] + v)
            dpi[j] = t
    for v, L in vL:
        if v < H:
            print(dp[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4,i4,i4[:],i4[:],i4[:],i4[:])',cache=True)
def main(prev,remain,q,v,w,vq,lq):
    dp = np.zeros((2**prev+1,10**5+1),np.int32)
    for i in range(1,2**prev+1):
        vi = v[i]
        wi = w[i]
        dp[i]=dp[i//2]
        for j in range(wi,10**5+1):
            dp[i][j] = max(dp[i][j],dp[i//2][j-wi]+vi)
    for i in range(q):
        V,L= vq[i],lq[i]
        if V <= 2**prev:
            print(dp[V][L])
        else:
            ans = 0
            for j in range(2**remain):
                cur = V
                curw = 0
                curv = 0
                while cur > 2**prev:
                    if j & 1:
                        curv += v[cur]
                        curw += w[cur]
                    cur //= 2
                    j >>= 1
                if curw <= L:
                    ans = max(ans,dp[cur][L-curw]+curv)
            print(ans)

n = int(readline())
stdin = np.array(read().split(),np.int32)
v = np.zeros(n+1,np.int32)
w = np.zeros(n+1,np.int32)
v[1:] = stdin[:2*n:2]
w[1:] = stdin[1:2*n:2]
q = stdin[2*n]
query = stdin[2*n+1:]
vq = query[::2]
lq = query[1::2]
k = 0
num = 1
while num < n:
    k += 1
    num *= 2
prev = k//2
remain = k-k//2
main(prev,remain,q,v,w,vq,lq)

Submission status: Time Limit Exceeded

Solution code:
import sys
MX = 10**5
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(MX + 1):
            t = dpip[j]
            if j >= w:
                t = max(t, dpip[j - w] + v)
            dpi[j] = t
    for v, L in vL:
        if v < H:
            print(dp[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    value += items[node - 1][0]
                    weight += items[node - 1][1]
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    MX = 10**5
    dp1 = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        for j in range(MX + 1):
            dp1[i][j] = dp1[i >> 1][j]
            if j >= w:
                dp1[i][j] = max(dp1[i][j], dp1[i >> 1][j - w] + v)
    for v, L in vL:
        if v < H:
            print(dp1[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    value += items[node - 1][0]
                    weight += items[node - 1][1]
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp1[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def filter(w1,w2,v):
    if w2<=w1:
        return v
    else:
        return 0

def main():
    N=int(input())
    V=[]
    W=[]
    for i in range(N):
        v,w=map(int,input().split())
        V.append(v)
        W.append(w)
    Q=int(input())
    v=[]
    L=[]
    for i in range(Q):
        v_,l=map(int,input().split())
        v.append(v_)
        L.append(l)
    M=max(L)
    D= int(math.sqrt(N+1))#bound of tree
    if D>=2:
        D=D*2//3

    #knapsack DP
    dp=[[filter(w,W[v],V[v]) for w in range(M+1)] for v in range(N)]
    for i in range(1, pow(2, D) - 1):
        for w in range(1,M+1):
            if (w>=W[i]):
                dp[i][w]=max(dp[(i-1)//2][w-W[i]]+V[i],dp[(i-1)//2][w])
            else:
                dp[i][w]=dp[(i-1)//2][w]

    BoundIndex=pow(2,D)-2

    for q in range(Q):
        if v[q]-1>BoundIndex:
            d=int(math.sqrt(v[q]))+1
            k=d-D
            ALL=pow(2,k)
            rest_v=[v[q]-1]
            v_=v[q]-1
            for _ in range(k-1):
                v_=(v_-1)//2
                rest_v.append(v_)

            parent_node=(v_-1)//2

            form='0'+str(k)+'b'

            res=0
            for a in range(ALL):
                a_bin=format(a,form)
                restW=0
                restV=0
                for flag_index in range(k):
                    if a_bin[flag_index]=="1":
                        ind=rest_v[flag_index]
                        restW+=W[ind]
                        restV+=V[ind]
                if L[q]-restW>=0:
                    res=max(res,restV+dp[parent_node][L[q]-restW])

            print(res)
        else:
            print(dp[v[q]-1][L[q]])



    # for q in range(Q):
    #     print(dp[v[q]-1][L[q]])





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def filter(w1,w2,v):
    if w2<=w1:
        return v
    else:
        return 0

def main():
    N=int(input())
    V=[]
    W=[]
    for i in range(N):
        v,w=map(int,input().split())
        V.append(v)
        W.append(w)
    Q=int(input())
    v=[]
    L=[]
    for i in range(Q):
        v_,l=map(int,input().split())
        v.append(v_)
        L.append(l)
    M=max(L)
    D= int(math.sqrt(N+1))#bound of tree
    if D>=2:
        D//=2

    #knapsack DP
    dp=[[filter(w,W[v],V[v]) for w in range(M+1)] for v in range(N)]
    for i in range(1, pow(2, D) - 1):
        for w in range(1,M+1):
            if (w>=W[i]):
                dp[i][w]=max(dp[(i-1)//2][w-W[i]]+V[i],dp[(i-1)//2][w])
            else:
                dp[i][w]=dp[(i-1)//2][w]

    BoundIndex=pow(2,D)-2

    for q in range(Q):
        if v[q]-1>BoundIndex:
            d=int(math.sqrt(v[q]))+1
            k=d-D
            ALL=pow(2,k)
            rest_v=[v[q]-1]
            v_=v[q]-1
            for _ in range(k-1):
                v_=(v_-1)//2
                rest_v.append(v_)

            parent_node=(v_-1)//2

            form='0'+str(k)+'b'

            res=0
            for a in range(ALL):
                a_bin=format(a,form)
                restW=0
                restV=0
                for flag_index in range(k):
                    if a_bin[flag_index]=="1":
                        ind=rest_v[flag_index]
                        restW+=W[ind]
                        restV+=V[ind]
                if L[q]-restW>=0:
                    res=max(res,restV+dp[parent_node][L[q]-restW])

            print(res)
        else:
            print(dp[v[q]-1][L[q]])



    # for q in range(Q):
    #     print(dp[v[q]-1][L[q]])





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  def solve(L,Ddp,y,l):
    ans = 0
    length = len(l)
    for i in range(2**length):
      a,b = 0,0
      for j in range(length):
        if i>>j&1:
          vw = l[j]
          a += vw[0]
          b += vw[1]

        if b>L:
          break
      if b>L:
        continue
      else:
        ans = max(ans, Ddp[y][L-b] + a)
    return ans
  
  def dp():
    Ddp = tuple([[0] * (M_plu) for _ in range(multiplier)])
    mi_mul = multiplier-1
    tmp = tuple(VW[:mi_mul])
    for i,(V,W) in enumerate(tmp,1):
      x = i//2
      for j in range(M_plu):
        if W<=j:
          Ddp[i][j] = max(Ddp[x][j-W] + V, Ddp[x][j])
        else:
          Ddp[i][j] = Ddp[x][j]
    return Ddp

  import sys
  input = sys.stdin.readline
  import math
  from collections import deque
  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)]
  M = 0
  for v,L in vL:
    M = max(L,M)
    
  D = int(math.log2(N)) + 1
  K = D//18 * 11
  multiplier = 2**K
  M_plu = M+1
  mi_mul = multiplier-1
  

  Ddp = dp()
        
  for v,L in vL:
    if v<=mi_mul:
      print(Ddp[v][L])
      continue
      
    else:
      y = v
      l = deque([])
      x = int(math.log2(v)) + 1
      x_K = x-K
      for i in range(x_K):
        vw = VW[y-1]
        if vw[1]<=L:
          l.append(vw)
        y //= 2
      ans = solve(L,Ddp,y,l)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  def solve(L,Ddp,y,l):
    ans = 0
    length = len(l)
    for i in range(2**length):
      a,b = 0,0
      for j in range(length):
        if i>>j&1:
          vw = l[j]
          a += vw[0]
          b += vw[1]

        if b>L:
          break
      if b>L:
        continue
      else:
        ans = max(ans, Ddp[y][L-b] + a)
    return ans
  
  def dp():
    Ddp = tuple([[0] * (M_plu) for _ in range(multiplier)])
    mi_mul = multiplier-1
    tmp = tuple(VW[:mi_mul])
    for i,(V,W) in enumerate(tmp,1):
      x = i//2
      for j in range(M_plu):
        if W<=j:
          Ddp[i][j] = max(Ddp[x][j-W] + V, Ddp[x][j])
        else:
          Ddp[i][j] = Ddp[x][j]
    return Ddp

  import sys
  input = sys.stdin.readline
  import math
  from collections import deque
  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)]
  M = 0
  for v,L in vL:
    M = max(L,M)
    
  D = int(math.log2(N)) + 1
  K = D//9 * 5
  multiplier = 2**K
  M_plu = M+1
  mi_mul = multiplier-1
  

  Ddp = dp()
        
  for v,L in vL:
    if v<=mi_mul:
      print(Ddp[v][L])
      continue
      
    else:
      y = v
      l = deque([])
      x = int(math.log2(v)) + 1
      x_K = x-K
      for i in range(x_K):
        vw = VW[y-1]
        if vw[1]<=L:
          l.append(vw)
        y //= 2
      ans = solve(L,Ddp,y,l)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():

    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 32 - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():

    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 64 - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in reversed(range(w, L_MAX + 1)):
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 10
V_MAX = (1 << D_TH) - 64 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i + 1) >> 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 10
V_MAX = (1 << D_TH) + 64 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 378 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 256 - 1
dp = [[0] * (L_MAX + 1)]
# items = []
items_v = []
items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

# items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            # vv.append(items[v - V_MAX][0])
            # ww.append(items[v - V_MAX][1])
            vv.append(items_v[v - V_MAX])
            ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 256 - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in reversed(range(w, L_MAX + 1)):
            if dp_[j] < dp_[j - w] + val:
                dp_[j] = dp_[j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 100 - 1
dp = [[0] * (L_MAX + 1)]
items = []
# items_v = []
# items_w = []

for i in range(n):
    val, w = map(int, input().split())
    if i < V_MAX:
        i1 = i + 1
        i0 = (i - 1) // 2 + 1
        dp_ = dp[i0][:]

        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            if dp_[j] < dp[i0][j - w] + val:
                dp_[j] = dp[i0][j - w] + val
        dp.append(dp_)
    else:
        items.append((val, w))
        # items_v.append(val)
        # items_w.append(w)

items = tuple(items)

q = int(input())
for _ in range(q):
    v, l = map(int, input().split())
    v -= 1

    if v < V_MAX:
        ans = dp[v + 1][l]
    else:
        vv = []
        ww = []
        while v >= V_MAX:
            vv.append(items[v - V_MAX][0])
            ww.append(items[v - V_MAX][1])
            # vv.append(items_v[v - V_MAX])
            # ww.append(items_w[v - V_MAX])
            v = (v - 1) >> 1

        ans = dp[v + 1][l]
        # m = len(vv)
        m2 = 1 << len(vv)
        v_sub = [0] * m2
        w_sub = [0] * m2
        for bit in range(1, m2):
            bit_min = bit & (-bit)
            x = bit_min.bit_length() - 1

            s_w = w_sub[bit - bit_min] + ww[x]
            w_sub[bit] = s_w
            if s_w <= l:
                s_val = v_sub[bit - bit_min] + vv[x]
                v_sub[bit] = s_val
                ans = max(ans, dp[v + 1][l - s_w] + s_val)

    print(ans)