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: Wrong Answer

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 = len(b) - 1
    for w, v in a:
        if i < 0:
            break
        if b[i][0] + w > L:
            i -= 1
            continue
        res = max(res, v + b[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(1025)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N, 1024) + 1):
        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: Wrong Answer

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
      for i in range(x - K):
        vw = VW[y-1]
        if vw[1]<=L:
          l.append(vw)
        y //= 2
      ans = 0
      length = len(l)
main()

Submission status: Wrong Answer

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:
      x = Ddp[v][L]
      print(x)
      continue
main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)]
  
  tmp = multiplier-1
  tmp = VW[:tmp]
  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<=2**K - 1:
      print(Ddp[v][L])
      continue
main()

Submission status: Wrong Answer

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)]
  
  tmp = multiplier-1
  tmp = VW[:tmp]
  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 q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
main()

Submission status: Wrong Answer

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)]
  
  tmp = multiplier-1
  tmp = VW[:tmp]
  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]
main()

Submission status: Wrong Answer

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)]
  
  for i,(V,W) in enumerate(VW[:multiplier-1],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]
main()

Submission status: Wrong Answer

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)]
  
  for i,(V,W) in enumerate(VW[:multiplier-1],1):
    V,W = VW[i-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]
main()

Submission status: Wrong Answer

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)]
  
  for i in range(1,multiplier):
    V,W = VW[i-1]
    x = i//2
    for j in range(M_plu):
      if W<=j:
        y = j-W
        Ddp[i][j] = max(Ddp[x][y] + V, Ddp[x][j])
      else:
        Ddp[i][j] = Ddp[x][j]
main()

Submission status: Wrong Answer

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)]
  
  for i in range(1,multiplier):
    V,W = VW[i-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]
main()

Submission status: Wrong Answer

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)]
  
  for i in range(1,multiplier):
    V,W = VW[i-1]
    for j in range(M_plu):
      if W<=j:
        Ddp[i][j] = max(Ddp[i//2][j-W] + V, Ddp[i//2][j])
      else:
        Ddp[i][j] = Ddp[i//2][j]
main()

Submission status: Wrong Answer

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)]
  
  for i in range(1,2**K):
    V,W = VW[i-1]
    for j in range(M+1):
      if W<=j:
        Ddp[i][j] = max(Ddp[i//2][j-W] + V, Ddp[i//2][j])
      else:
        Ddp[i][j] = Ddp[i//2][j]
main()

Submission status: Wrong Answer

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
  Ddp = [[0] * (M+1) for _ in range(multiplier)]

main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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
  Ddp = [[0 for _ in range(M+1)] for _ in range(2**K)]

main()

Submission status: Wrong Answer

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
  Ddp = [[0] * (M+1) for _ in range(2**K)]

main()

Submission status: Wrong Answer

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

    for i in range(n):
        val, w = map(int, input().split())
        items.append((val, w))
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) // 2
            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)

    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:
            items_sub = [items[v]]
            while v >= V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

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

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:
    if L>M:
      M = L
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
M = 10**5
VW = [(0, 0)] + [tuple(map(int, input().split())) for i in range(N)]

dp = [[0] * (M+1) for i in range(512)]
for i in range(1, 512):
  if i > N:
    break
  v, w = VW[i]
  par = i//2
  for wi in range(M+1):
    if wi < w:
      dp[i][wi] = dp[par][wi]
    else:
      dp[i][wi] = max(dp[par][wi], dp[par][wi-w]+v)

def enum(node):
  res = []
  while node > 511:
    res.append(node)
    node //= 2
  return res, node

def calc(node, L):
  nodes, par = enum(node)
  cands = []
  res = 0
  for node in nodes:
    v, w = VW[node]
    temp = [(vi+v, wi+w) for vi, wi in cands]
    cands += temp
  for v, w in cands:
    if w <= L:
      res = max(res, dp[par][L-w] + v)
  return res

Q = int(input())
ans = []
for q in range(Q):
  node, L = map(int, input().split())
  if node <= 511:
    ans.append(dp[node][L])
  else:
    ans.append(calc(node, L))

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

Submission status: Wrong Answer

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 q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x
main()

Submission status: Wrong Answer

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
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  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
  import math
  from collections import deque
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(10**5):
    print(1)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = deque([[0] * (M+1) for _ in range(2**K)])

  for q in range(10**5):
    print(1)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = deque([[0] * (M+1) for _ in range(2**K)])

  for q in range(10**5):
    print(1)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = deque([[0] * (M+1) for _ in range(2**K)])

  for q in range(Q):
    continue
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = deque([[0] * (M+1) for _ in range(2**K)])

  for q in range(Q):
    print(1)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  import numpy as np
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = np.array([[0] * (M+1) for _ in range(2**K)])

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = dict()
  for i in range(2**K):
    Ddp[i] = [0]*(M+1)

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = deque([[0] * (M+1) for _ in range(2**K)])

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = tuple(data[:2*n:2])
W = tuple(data[1:2*n:2])
q = data[2*n]
v = tuple(data[2*n+1::2])
L = tuple(data[2*n+2::2])

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(9, n.bit_length()-1)
max_bef = 2**b_len
bef = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    iw,iv = W[i-1],V[i-1]
    par = i//2
    for j in range(1,10**5+1):
        if(j>=iw):
            bef[i][j] = max(bef[par][j] , bef[par][j-iw]+iv)
        else:
            bef[i][j] = bef[par][j]

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    par = vi
    while(par>= max_bef):
        par //= 2

    max_ans = bef[par][Li]
    aft = [(0,0)]
    x = vi
    while(x >= max_bef):
        xw,xv = W[x-1],V[x-1]
        x //= 2
        if(x < max_bef):
            for jw,jv in aft:
                lim_w = Li - (jw+xw)
                if(lim_w >= 0):
                    max_ans = max(max_ans, bef[par][lim_w]+jv+xw)
            break

        aft2 = []
        for jw,jv in aft:
            jw += xw
            jv += xv
            lim_w = Li - (jw)
            if(lim_w >= 0):
                max_ans = max(max_ans, bef[par][lim_w]+jv)
                aft2.append((jw,jv))

        aft = aft + aft2

    ans.append(max_ans)

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

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = [[0] * (M+1) for _ in range(2**K)]

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = tuple(data[:2*n:2])
W = tuple(data[1:2*n:2])
q = data[2*n]
v = tuple(data[2*n+1::2])
L = tuple(data[2*n+2::2])

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(9, n.bit_length()-1)
max_bef = 2**b_len
bef = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    iw,iv = W[i-1],V[i-1]
    par = i//2
    for j in range(1,10**5+1):
        if(j>=iw):
            bef[i][j] = max(bef[par][j] , bef[par][j-iw]+iv)
        else:
            bef[i][j] = bef[par][j]

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    par = vi
    while(par>= max_bef):
        par //= 2

    max_ans = bef[par][Li]
    aft = [(0,0)]
    x = vi
    while(x >= max_bef):
        xw,xv = W[x-1],V[x-1]
        x //= 2
        if(x >= max_bef):
            for jw,jv in aft:
                lim_w = Li - (jw+xw)
                if(lim_w >= 0):
                    max_ans = max(max_ans, bef[par][lim_w]+jv+xw)
            break

        aft2 = []
        for jw,jv in aft:
            jw += xw
            jv += xv
            lim_w = Li - (jw)
            if(lim_w >= 0):
                max_ans = max(max_ans, bef[par][lim_w]+jv)
                aft2.append((jw,jv))

        aft = aft + aft2

    ans.append(max_ans)

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

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D
  Ddp = [[0] * (M+1) for _ in range(2**K)]

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D*9//10
  Ddp = [[0] * (M+1) for _ in range(2**K)]

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D
  Ddp = [[0] * (M+1) for _ in range(2**K)]

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    else:
      y = v
      l = deque([])
      x = int(math.log2(v)) + 1
      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):
        z = [0,0]
        for j in range(length):
          if i>>j&1:
            vw = l[j]
            z[0] += vw[0]
            z[1] += vw[1]

          if z[1]>L:
            break
        if z[1]>L:
          continue
        else:
          ans = max(ans, Ddp[y][L-z[1]] + z[0])

    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = [[0] * (M+1) for _ in range(2**K)]

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    else:
      y = v
      l = deque([])
      x = int(math.log2(v)) + 1
      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):
        z = [0,0]
        for j in range(length):
          if i>>j&1:
            vw = l[j]
            z[0] += vw[0]
            z[1] += vw[1]

          if z[1]>L:
            break
        if z[1]>L:
          continue
        else:
          ans = max(ans, Ddp[y][L-z[1]] + z[0])

    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
def main():  
  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
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D*9//10
  Ddp = [[0] * (M+1) for _ in range(2**K)]

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    else:
      y = v
      l = deque([])
      x = int(math.log2(v)) + 1
      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):
        z = [0,0]
        for j in range(length):
          if i>>j&1:
            vw = l[j]
            z[0] += vw[0]
            z[1] += vw[1]

          if z[1]>L:
            break
        if z[1]>L:
          continue
        else:
          ans = max(ans, Ddp[y][L-z[1]] + z[0])

    print(ans)
    
main()