Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

0
3
3

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

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

Sample Input 2

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

Sample Output 2

256
255
250
247
255
259
223
253



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


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    IV, IW = [], []

    H = min(N + 1, 1 << 10)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    i = 1
    for v, w in zip(data, data):
        if i < H:
            IV.append(v)
            IW.append(w)
            dpi = dp[i]
            dpip = dp[i >> 1]
            for j in range(w):
                dpi[j] = dpip[j]
            for j in range(w, MX + 1):
                dpi[j] = max(dpip[j], dpip[j - w] + v)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue
        ans = []
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    value += IV[node - 1]
                    weight += IW[node - 1]
                    if weight > L:
                        break
                node >>= 1
                i >>= 1
            else:
                ans.append(value + dp[node][L - weight])
        print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for _ in range(N):
  v, w = map(int, input().split())
  a.append((w, v))
  W += w
n = min(N, max(9, N >> 1))
dp = [[0] * (W + 1) for _ in range(n + 1)]
for j in range(a[1][0], W + 1): dp[1][j] = a[1][1]
for i in range(1, n + 1):
  #print(i, i * 2, i * 2 + 1)
  for j in range(W + 1):
    if i * 2 <= n:
      if j + a[i * 2][0] <= W: dp[i * 2][j + a[i * 2][0]] = max(dp[i * 2][j + a[i * 2][0]], dp[i][j] + a[i * 2][1])
      dp[i * 2][j] = max(dp[i * 2][j], dp[i][j])
    if i * 2 + 1 <= n:
      if j + a[i * 2 + 1][0] <= W: dp[i * 2 + 1][j + a[i * 2 + 1][0]] = max(dp[i * 2 + 1][j + a[i * 2 + 1][0]], dp[i][j] + a[i * 2 + 1][1])
      dp[i * 2 + 1][j] = max(dp[i * 2 + 1][j], dp[i][j])
#print(n)
#print(dp[4][: 234])
"""
Q = int(input())
for _ in range(Q):
  x, l = map(int, input().split())
  if x <= n:
    print(dp[x][min(W, l)])
    continue
  order = [x]
  while order[-1] > n: order.append(order[-1] >> 1)
  dpq = dp[order[-1]][: ]
  order.reverse()
  #print(order)
  for i in range(len(order) - 1):
    p = order[i]
    q = order[i + 1]
    for j in range(W, -1, -1):
      if j + a[q][0] <= W: dpq[j + a[q][0]] = max(dpq[j + a[q][0]], dpq[j] + a[q][1])
  print(dpq[min(W, l)])
"""

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for _ in range(N):
  v, w = map(int, input().split())
  a.append((w, v))
  W += w
n = min(N, max(9, N >> 1))
dp = [[0] * (W + 1) for _ in range(n + 1)]
for j in range(a[1][0], W + 1): dp[1][j] = a[1][1]
for i in range(1, n + 1):
  #print(i, i * 2, i * 2 + 1)
  for j in range(W + 1):
    if i * 2 <= n:
      if j + a[i * 2][0] <= W: dp[i * 2][j + a[i * 2][0]] = max(dp[i * 2][j + a[i * 2][0]], dp[i][j] + a[i * 2][1])
      dp[i * 2][j] = max(dp[i * 2][j], dp[i][j])
    if i * 2 + 1 <= n:
      if j + a[i * 2 + 1][0] <= W: dp[i * 2 + 1][j + a[i * 2 + 1][0]] = max(dp[i * 2 + 1][j + a[i * 2 + 1][0]], dp[i][j] + a[i * 2 + 1][1])
      dp[i * 2 + 1][j] = max(dp[i * 2 + 1][j], dp[i][j])
#print(n)
#print(dp[4][: 234])
Q = int(input())
for _ in range(Q):
  x, l = map(int, input().split())
  if x <= n:
    print(dp[x][min(W, l)])
    continue
  order = [x]
  while order[-1] > n: order.append(order[-1] >> 1)
  dpq = dp[order[-1]][: ]
  order.reverse()
  #print(order)
  for i in range(len(order) - 1):
    p = order[i]
    q = order[i + 1]
    for j in range(W, -1, -1):
      if j + a[q][0] <= W: dpq[j + a[q][0]] = max(dpq[j + a[q][0]], dpq[j] + a[q][1])
  print(dpq[min(W, l)])

Submission status: Runtime Error

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

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

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

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

dfs(dp, 1)
Q = ir()
Z = []

def dfs_rev(dp, i):
    assert i > N // 2
    v, w = VW[i-1]
    next = dp.copy()
    next[w:] = np.maximum(dp[w:], dp[:-w] + v)
    X[i] = next
    if i // 2 > N // 2:
        return dfs(next, i // 2)
    else:
        return (next, i // 2)

for _ in range(Q):
    v, L = lr()
    if v <= N // 2:
        Z.append(X[v][L])
    else:
        down, parent = dfs_rev(dp, v)
        up = X[parent]
        #print(up[:L], down[:L], parent)
        union = up[:L+1] + down[:L+1][::-1]
        ans = np.max(union)
        Z.append(ans)

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

Submission status: Runtime Error

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

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

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

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

dfs(dp, 1)
Q = ir()
Z = []

def dfs_rev(dp, i):
    assert i > N // 2
    v, w = VW[i-1]
    next = dp.copy()
    next[w:] = np.maximum(dp[w:], dp[:-w] + v)
    X[i] = next
    if i // 2 > N // 2:
        return dfs(next, 2*i)
    else:
        return (next, i // 2)

for _ in range(Q):
    v, L = lr()
    if v <= N // 2:
        Z.append(X[v][L])
    else:
        down, parent = dfs_rev(dp, v)
        up = X[parent]
        #print(up[:L], down[:L], parent)
        union = up[:L+1] + down[:L+1][::-1]
        ans = np.max(union)
        Z.append(ans)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for _ in range(N):
  v, w = map(int, input().split())
  a.append((w, v))
  W += w
n = N >> 1
dp = [[0] * (W + 1) for _ in range(n + 1)]
for j in range(a[1][0], W + 1): dp[1][j] = a[1][1]
for i in range(1, n + 1):
  #print(i, i * 2, i * 2 + 1)
  for j in range(W + 1):
    if i * 2 <= n:
      if j + a[i * 2][0] <= W: dp[i * 2][j + a[i * 2][0]] = max(dp[i * 2][j + a[i * 2][0]], dp[i][j] + a[i * 2][1])
      dp[i * 2][j] = max(dp[i * 2][j], dp[i][j])
    if i * 2 + 1 <= n:
      if j + a[i * 2 + 1][0] <= W: dp[i * 2 + 1][j + a[i * 2 + 1][0]] = max(dp[i * 2 + 1][j + a[i * 2 + 1][0]], dp[i][j] + a[i * 2 + 1][1])
      dp[i * 2 + 1][j] = max(dp[i * 2 + 1][j], dp[i][j])
#print(n)
#print(dp[4][: 234])
Q = int(input())
for _ in range(Q):
  x, l = map(int, input().split())
  if x <= n:
    print(dp[x][min(W, l)])
    continue
  order = [x]
  while order[-1] > n: order.append(order[-1] >> 1)
  dpq = dp[order[-1]][: ]
  order.reverse()
  #print(order)
  for i in range(len(order) - 1):
    p = order[i]
    q = order[i + 1]
    for j in range(W, -1, -1):
      if j + a[q][0] <= W: dpq[j + a[q][0]] = max(dpq[j + a[q][0]], dpq[j] + a[q][1])
  print(dpq[min(W, l)])

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heappush

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


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

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


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

            print(ans)

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

solve()

Submission status: Runtime Error

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][0]
                    weight += items[node][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: Runtime Error

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.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][0]
                    weight += items[node][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: Runtime Error

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(V_MAX):
        val, w = map(int, input().split())
        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_)

    for i in range(V_MAX, n):
        val, w = map(int, input().split())

        # 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: Runtime Error

Solution code:
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
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
  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: Runtime Error

Solution code:
def solve():
  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)
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)
      solve()
    print(ans)
main()

Submission status: Runtime Error

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 = 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: Runtime Error

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):
        z = [0,0]
        for j in range(length):

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

    print(ans)
main()

Submission status: Runtime Error

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 b[i][0] + w > L:
            i -= 1
            continue
        if i < 0:
            break
        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: Runtime Error

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

Submission status: Runtime Error

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: Runtime Error

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 = (0, ) + tuple(data[:2*N:2])
W = (0, ) + tuple(data[1:2*N:2])
Q = data[2*N]
NODE = tuple(data[2*N+1::2])
L = tuple(data[2*N+2::2])
 
bound = 512
M = max(L)

dp = [[0] * (M+1) for i in range(bound)]
for i in range(1, bound):
  if i > N:
    break
  v, w = V[i], W[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 calc(node, L):
  value = 0
  res = [(0, 0)]
  while node >= bound:
    v, w = VW[node]
    temp = [(vi+v, wi+w) for vi, wi in res if wi+w<=L]
    res += temp
    node //= 2
  for v, w in res:
    value = max(value, dp[node][L-w] + v)
  return value

ans = []
for node, l in zip(NODE, L):
  if node < bound:
    ans.append(dp[node][l])
  else:
    ans.append(calc(node, l))

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

Submission status: Runtime Error

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

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]

def solve(v,L):
    t=[]
    while v>=2**9:
        t.append(vw[v])
        v//=2
    n=len(t)
    for i in range(1,2**n):
        m=i.bit_length()
        temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
    ans=0
    for i in range(2**n):
        if L>=temp[i][1]:
            ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]])
    return ans

def main():
    for i in range(int(input())):
        print(solve(map(int,input().split())))

if __name__=="__main__":
    main()

Submission status: Runtime Error

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):
  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: Runtime Error

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

# 前処理
b_len = min(10, n.bit_length()-1)
max_bef = 2**b_len

bef = [ [] for _ in range(2**b_len)]
bef[1] = [(0,0),(W[0],V[0])]

for i in range(2,max_bef):
    iw,iv = W[i-1],V[i-1]
    j = i//2
    while(j > 0):
        for jw,jv in bef[j]:
            bef[i].append((iw+jw,iv+jv))
        j //= 2

bef_max = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    j = i
    while(j > 0):
        for jw,jv in bef[j]:
            bef_max[i][jw] = max(bef_max[i][jw], jv)
        j //= 2

    for j in range(1,10**5+1):
        bef_max[i][j] = max(bef_max[i][j],bef_max[i][j-1])

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

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

    ans.append(max_ans)

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

Submission status: Runtime Error

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

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**10)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**10,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(w):
        dp[i][j]=dp[i//2][j]
    for j in range(w,100001):
        dp[i][j]=max(dp[i//2][j],dp[i//2][j-w]+v)

temp=[[0,0] for i in range(2**n)]
for i in range(int(input())):
    v,L=map(int,input().split())
    if 2**10>v:
        print(dp[v][L])
    else:
        t=[]
        while v>=2**10:
            t.append(vw[v])
            v//=2
        n=len(t)
        temp[0][0]=0
        temp[0][0]=0
        for i in range(1,2**n):
            m=i.bit_length()
            temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
            temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
        ans=0
        for i in range(2**n):
            if L>=temp[i][1]:
                ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]])
        print(ans)

Submission status: Runtime Error

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)

memo = {}
def calc1(node):
  global memo
  if node in memo:
    return memo[node]
  v, w = VW[node]
  res, par = calc1(node // 2)
  add = [(tv+v, tw+w) for tv, tw in res]
  res += add
  memo[node] = (res, par)
  return res, par


def calc2(node, L):
  res = 0
  cands, par = calc1(node)
  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(calc2(node, L))

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