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
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 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)

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.append(dp[i0][:])
        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            if dp[i1][j] < dp[i0][j - w] + val:
                dp[i1][j] = dp[i0][j - w] + val
    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) - 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.append(dp[i0][:])
        # for j in range(w):
        #     dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    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:
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//2
  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:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 300 - 1
dp = [[0] * (L_MAX + 1) for _ in range(V_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
        for j in range(w):
            dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

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) for _ in range(V_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
        for j in range(w):
            dp[i1][j] = dp[i0][j]
        for j in range(w, L_MAX + 1):
            dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

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(w_sub)
        # print(v_sub)
        # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

    print(ans)

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

  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//2
  multiplier = 2**K
  M_plu = M+1
  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]
        
  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 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 main():
  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//2
  multiplier = 2**K
  M_plu = M+1
  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]
        
  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:
import sys
input = sys.stdin.readline

n = int(input())

L_MAX = 10**5
D_TH = 9
V_MAX = (1 << D_TH) + 50 - 1
dp = [[0] * (L_MAX + 1) for _ in range(V_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
        for j in range(L_MAX + 1):
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
    else:
        # items.append((val, w))
        items_v.append(val)
        items_w.append(w)

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(w_sub)
        # print(v_sub)
        # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  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//2
  multiplier = 2**K
  M_plu = M+1
  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]
  
  Ddp = tuple(map(tuple,Ddp))
  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 = 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)
    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 = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_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
            for j in range(L_MAX + 1):
                if j < w:
                    dp[i1][j] = dp[i0][j]
                else:
                    dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    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(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  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//2
  multiplier = 2**K
  M_plu = M+1
  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]
        
  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 = 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)
    print(ans)
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 = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

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

    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])
                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(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def merge(a, b):
    res = []
    i, j = 0, 0
    while i < len(a) or j < len(b):
        if j >= len(b) or (i < len(a) and a[i][0] < b[j][0]):
            w, v = a[i]
            i += 1
        else:
            w, v = b[j]
            j += 1
        if not res or (res[-1][1]) < v:
            res.append((w, v))
        elif res[-1][0] == w and res[-1][1] <= v:
            res.pop()
            res.append((w, v))
    return res


def best(L, a, b):
    res = 0
    i = 0
    j = len(b) - 1
    # for w, v in a:
    while i < len(a):
        w, v = a[i]
        if j < 0:
            break
        if b[j][0] + w > L:
            j -= 1
            continue
        res = max(res, v + b[j][1])
        i += 1
    return res


def main():
    N = int(input())
    VW = [(-1, -1)] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    query = tuple(tuple(map(int, input().split())) for _ in range(Q))

    dp = [[] for _ in range(1024)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N + 1, 1024)):
        vi, wi = VW[i]
        a1 = dp[i // 2]
        a2 = [(w + wi, v + vi) for w, v in a1]
        dp[i] = merge(a1, a2)

    for n, L in query:
        if n < 1024:
            w, v = zip(*dp[n])
            i = bisect.bisect_right(w, L) - 1
            print(v[i])
        else:
            a = [(0, 0)]
            while n >= 1024:
                vi, wi = VW[n]
                b = [(w + wi, v + vi) for w, v in a]
                a = merge(a, b)
                n //= 2
            print(best(L, a, dp[n]))


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 = 9
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

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

    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])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                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(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        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 = 8
    V_MAX = (1 << D_TH) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

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

    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])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                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(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        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) + 50 - 1
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]
    items = []

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

    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])
                v = (v - 1) // 2

            ans = dp[v + 1][l]
            m = len(vv)
            v_sub = [0] * (1 << m)
            w_sub = [0] * (1 << m)
            for bit in range(1, 1 << m):
                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(w_sub)
            # print(v_sub)
            # print([dp[v + 1][l - w_sub[i]] + v_sub[i] for i in range(1 << m)])

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  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//2
  multiplier = 2**K
  M_plu = M+1
  Ddp = [[0] * (M_plu) for _ in range(multiplier)]
  
  mi_mul = multiplier-1
  tmp = 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]
        
  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 = 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)
    print(ans)
main()