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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    return
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    return
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

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*3//5
  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:
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)
bef = [ [0]*(10**5 + 1) for _ in range(2**b_len)]

for i in range(1,2**b_len):
    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]

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

Submission status: Wrong Answer

Solution code:
N = int(input())
dame = 10**5+1
point = [[0 for weight in range(dame)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大

for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, min(W + maW[(k//2)]+1, dame)):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(point[v][min(L, maW[v])])

Submission status: Wrong Answer

Solution code:
N = int(input())
point = [[0 for weight in range(10**7)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大
for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, W + maW[(k//2)]+1):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[k//2], W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(max(point[v][:L+1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
from collections import defaultdict
vw = defaultdict(lambda: None)

class Node():
    def __init__(self, index, wei, val):
        self.index = index
        self.wei = wei
        self.val = val
        global vw
        vw[index] = self
        self.dp = defaultdict(int)
        if self.index < 128:
            self.calc()

    def __repr__(self):
        return f'Node({self.index}, {self.wei}, {self.val})'

    @property
    def parent(self):
        if self.index != 1:
            global vw
            return vw[self.index//2]
        else:
            return None

    def calc(self):
        dp = self.dp
        if self.parent is not None:
            anc = self.parent
            while 1:
                adp = anc.dp
                for w, v in list(adp.items()):
                    if v > 0:
                        if self.wei+w in adp:
                            dp[self.wei+w] = max(self.val+v, adp[self.wei+w])
                        else:
                            dp[self.wei+w] = self.val+v
                if anc.parent is not None:
                    anc = anc.parent
                else:
                    break
            dp[self.wei] = self.val
        else:
            dp[self.wei] = self.val

    def search(self, lw):
        ans = 0
        cur = self
        while 1:
            for w, v in cur.dp.items():
                if w <= lw:
                    ans = max(ans, v)
            if cur.index > 1:
                cur = cur.parent
            else:
                break
        return ans

for i in range(1, n+1):
    v, w = map(int, input().split())
    Node(i, w, v)

q = int(input())

for _ in range(q):
    v, l = map(int, input().split())
    print(vw[v].search(l))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, V: "List[int]", W: "List[int]", Q: int, VV: "List[int]", LL: "List[int]"):
    MAX_L = max(LL)
    d = int(math.log(N, 2)) + 1
    #print(d)
    hd = d // 2
    max_m = 2 ** (d // 2) - 1
    dp = [{} for _ in range(max_m + 1)]
    dp[0] = {0: 0}
    for i in range(max_m):
        v, w = V[i], W[i]
        idx = i + 1
        par = idx // 2
        for ww, vv in dp[par].items():
            dp[idx][ww] = dp[par][ww]
        for ww, vv in dp[par].items():
            if ww + w in dp[idx]:
                dp[idx][ww + w] = max(dp[idx][ww + w], dp[par][ww] + v)
            else:
                dp[idx][ww + w] = dp[par][ww] + v
    items = []
    for i in range(max_m + 1):
        max_v = 0
        tmp = [0] * (MAX_L + 1)
        for j in range(MAX_L + 1):
            if j in dp[i]:
                max_v = max(max_v, dp[i][j])
            tmp[j] = max_v
        items.append(tmp)

    #print(dp)
    #print(items)
    return 0

    for q in range(Q):
        ret = 0
        idx, l = VV[q], LL[q]
        pre = {0: 0}
        while idx > max_m:
            w, v = W[idx - 1], V[idx - 1]
            cur = {ww: vv for ww, vv in pre.items()}
            for ww, vv in pre.items():
                if ww + w in cur:
                    cur[ww + w] = max(cur[ww + w], cur[ww] + v)
                else:
                    cur[ww + w] = cur[ww] + v
            pre = cur
            idx //= 2
        #print(pre, items[idx], l)
        for ww, vv in pre.items():
            if l < ww:
                continue
            max_l = l - ww
            vvv = items[idx][max_l]
            ret = max(ret, vv + vvv)

            ##x = bisect.bisect_right(items[idx], (max_l, float('inf')))
            ##if x < 1:
            ##    vvv = 0
            ##else:
            ##    vvv = items[idx][x - 1][1]
            ##ret = max(ret, vv + vvv)
            ###print(ww, vv, max_l, x, vvv, ret)
        print(ret)
        #print(' ************* ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    V = [int()] * (N)  # type: "List[int]"
    W = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        V[i] = int(next(tokens))
        W[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    v = [int()] * (Q)  # type: "List[int]"
    L = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        v[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, V, W, Q, v, L)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


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

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


depth = 1
while 2 ** depth - 1 < n:
    depth += 1

half_depth = depth // 2
half_last_node = 2 ** half_depth - 2

memos = []
DP = np.zeros(10**5+1, dtype=np.int64)
v0, w0 = items[0]
DP[w0:] = v0
memos.append(DP)

for node in range(1, half_last_node+1):
    parent = (node-1) // 2
    memo = memos[parent]

    value, weight = items[node]
    new_DP = np.hstack((memo[:weight], np.maximum(memo[:-weight] + value, memo[weight:])))
    memos.append(new_DP)


def calc_latter_half(node, limit):
    latter_items = []
    parent = node
    while parent > half_last_node:
        latter_items.append(items[parent])
        parent = (parent-1) // 2

    weights = []
    values = []
    item_count = len(latter_items)
    for bits in range(2**item_count):
        weight = 0
        value = 0
        for i in range(item_count):
            if (bits >> i) & 1:
                v, w = latter_items[i]
                weight += w
                value += v

        if weight > limit:
            continue

        weights.append(weight)
        values.append(value)

    return np.array(weights, np.int64), values, parent


def solve(query):
    node, limit = query
    node -= 1
    if node <= half_last_node:
        return (memos[node][limit])

    weights, latter_values, parent = calc_latter_half(node, limit)
    residues = limit - weights
    first_half_values = memos[parent][residues]
    candidates = first_half_values + latter_values
    return candidates.max()


answers = map(solve, queries)
for ans in answers:
    print(ans)

Submission status: Wrong Answer

Solution code:
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
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 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]
      

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

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

Submission status: Wrong Answer

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

    n = int(input())
    vw = [list(map(int, input().split())) for _ in [0]*n]
    q = int(input())
    vl = [list(map(int, input().split())) for _ in [0]*q]

    former = min(512, n)
    former_dp = [[-1]*100001 for _ in [0]*former]
    former_set = [set() for _ in [0]*former]

    former_dp[0][0] = 0
    former_dp[0][vw[0][1]] = vw[0][0]
    former_set[0] = {0, vw[0][1]}

    for i in range(1, former):
        v, w = vw[i]
        anc_dp = former_dp[(i-1)//2]
        now_dp = former_dp[i]
        anc_set = former_set[(i-1)//2]
        now_set = former_set[i]
        for j in anc_set:
            now_dp[j] = anc_dp[j]
            now_set.add(j)
        for j in anc_set:
            if w+j <= 100000:
                now_dp[w+j] = max(now_dp[w+j], anc_dp[j]+v)
                now_set.add(w+j)

    for i in range(former):
        m = 0
        now_dp = former_dp[i]
        for j in range(1, 100001):
            m = max(m, now_dp[j])
            now_dp[j] = m

    for v, l in vl:
        if v <= former:
            print(former_dp[v-1][l])
            continue
        later = []
        vv = v
        while vv > former:
            later.append(vw[vv-1])
            vv >>= 1
        anc_dp = former_dp[vv-1]
        m = len(later)
        ans = 0

        print(ans)

main()

Submission status: Wrong Answer

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

    n = int(input())
    vw = [list(map(int, input().split())) for _ in [0]*n]
    q = int(input())
    vl = [list(map(int, input().split())) for _ in [0]*q]

    former = min(512, n)
    former_dp = [[-1]*100001 for _ in [0]*former]
    former_set = [set() for _ in [0]*former]

    former_dp[0][0] = 0
    former_dp[0][vw[0][1]] = vw[0][0]
    former_set[0] = {0, vw[0][1]}

    for i in range(1, former):
        v, w = vw[i]
        anc_dp = former_dp[(i-1)//2]
        now_dp = former_dp[i]
        anc_set = former_set[(i-1)//2]
        now_set = former_set[i]
        for j in anc_set:
            now_dp[j] = anc_dp[j]
            now_set.add(j)
        for j in anc_set:
            if w+j <= 100000:
                now_dp[w+j] = max(now_dp[w+j], anc_dp[j]+v)
                now_set.add(w+j)

    for i in range(former):
        m = 0
        now_dp = former_dp[i]
        for j in range(1, 100001):
            m = max(m, now_dp[j])
            now_dp[j] = m


main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
V = [None]*n
W = [None]*n
for i in range(n):
    V[i],W[i] = map(int, input().split())

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]

until = min(n, 2**10-1)

def sub0(l, w, v):
    ll = list((ww+w, vv+v) for ww,vv in l)
    nl = [(0,0)]
    i1 = 0
    i2 = 0
    length = len(l)
    while i1<length or i2<length:
        if i1<length and (i2>=length or l[i1][0]<ll[i2][0]):
            if l[i1][1]>nl[-1][1]:
                nl.append(l[i1])
            i1 += 1
        elif i2<length:
            if ll[i2][1]>nl[-1][1]:
                nl.append(ll[i2])
            i2 += 1      
    return nl

# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        nl = sub0(l, W[v], V[v])
        d[v] = nl
#         print(l, ll, nl)
        q.appendleft(v)

from bisect import bisect_right as br
def sub(vv, L):
    if d[vv] is None:
        ll = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll = sub0(ll, W[vv], V[vv])
#             ll.extend(list((wt+W[vv], vt+V[vv]) for wt,vt in ll))
        tmp = ll
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = -1
    
    for w1,v1 in tmp:
        if w1>L:
            continue
        out = br(l, (L-w1, float("inf")))
        ans = max(ans, l[out-1][1]+v1)
    return ans
        
q = int(input())
ans = [None]*q
for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    ans[i] = sub(vv, ll)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
V = [None]*n
W = [None]*n
for i in range(n):
    V[i],W[i] = map(int, input().split())

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]

until = min(n, 2**10-1)

def sub0(l, w, v):
    ll = list((ww+w, vv+v) for ww,vv in l)
    nl = [(0,0)]
    i1 = 0
    i2 = 0
    length = len(l)
    while i1<length or i2<length:
        if i1<length and l[i1][0]<ll[i2][0]:
            if l[i1][1]>nl[-1][1]:
                nl.append(l[i1])
            i1 += 1
        elif i2<length:
            if ll[i2][1]>nl[-1][1]:
                nl.append(ll[i2])
            i2 += 1      
    return nl

# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        nl = sub0(l, W[v], V[v])
        d[v] = nl
#         print(l, ll, nl)
        q.appendleft(v)

from bisect import bisect_right as br
def sub(vv, L):
    if d[vv] is None:
        ll = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll = sub0(ll, W[vv], V[vv])
#             ll.extend(list((wt+W[vv], vt+V[vv]) for wt,vt in ll))
        tmp = ll
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = -1
    
    for w1,v1 in tmp:
        if w1>L:
            continue
        out = br(l, (L-w1, float("inf")))
        ans = max(ans, l[out-1][1]+v1)
    return ans
        
q = int(input())
ans = [None]*q
for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    ans[i] = sub(vv, ll)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
V = [None]*n
W = [None]*n
for i in range(n):
    V[i],W[i] = map(int, input().split())

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]

until = min(n, 2**3-1)

def sub0(l, w, v):
    ll = list((ww+w, vv+v) for ww,vv in l)
    nl = [(0,0)]
    i1 = 0
    i2 = 0
    length = len(l)
    while i1<length or i2<length:
        if i1<length and l[i1][0]<ll[i2][0]:
            if l[i1][1]>nl[-1][1]:
                nl.append(l[i1])
            i1 += 1
        elif i2<length:
            if ll[i2][1]>nl[-1][1]:
                nl.append(ll[i2])
            i2 += 1      
    return nl

# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        nl = sub0(l, W[v], V[v])
        d[v] = nl
#         print(l, ll, nl)
        q.appendleft(v)

from bisect import bisect_right as br
def sub(vv, L):
    if d[vv] is None:
        ll = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll = sub0(ll, W[vv], V[vv])
#             ll.extend(list((wt+W[vv], vt+V[vv]) for wt,vt in ll))
        tmp = ll
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = -1
    
    for w1,v1 in tmp:
        if w1>L:
            continue
        out = br(l, (L-w1, float("inf")))
        ans = max(ans, l[out-1][1]+v1)
    return ans
        
q = int(input())
ans = [None]*q
for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    ans[i] = sub(vv, ll)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma for _ in range(n2)]
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    # for i in range(1, n2):
    #     j = (i - 1) // 2
    #     l = 0
    #     aa, bb = vw[i]
    #     a = tab[j]
    #     for k in range(bb):
    #         tab[i][k] = a[k]
    #     for k in range(bb, ma):
    #         l = max((l, a[k - bb] + aa, a[k]))
    #         tab[i][k] = l

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [(0, 0)]
            while u >= n2:
                for i in a[:]:
                    if i[0] + vw[u][1] <= l:
                        a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
                u = (u - 1) // 2
            ans = 0
            b = tab[u]
            for i, j in a:
                ans = max(ans, b[l - i] + j)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
1

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma for _ in range(n2)]
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    for i in range(1, n2):
        j = (i - 1) // 2
        l = 0
        aa, bb = vw[i]
        a = tab[j]
        for k in range(bb):
            tab[i][k] = a[k]
        for k in range(bb, ma):
            l = max((l, a[k - bb] + aa, a[k]))
            tab[i][k] = l

    # q = int(input())
    # for _ in range(q):
    #     u, l = map(int, input().split())
    #     u -= 1
    #     if u < n2:
    #         print(tab[u][l])
    #     else:
    #         a = [(0, 0)]
    #         while u >= n2:
    #             for i in a[:]:
    #                 if i[0] + vw[u][1] <= l:
    #                     a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
    #             u = (u - 1) // 2
    #         ans = 0
    #         b = tab[u]
    #         for i, j in a:
    #             ans = max(ans, b[l - i] + j)
    #         print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma for _ in range(n2)]
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    for i in range(1, n2):
        j = (i - 1) // 2
        aa, bb = vw[i]
        a = tab[j]
        for k in range(bb):
            tab[i][k] = a[k]
        for k in range(bb, ma):
            tab[i][k] = max((tab[i][k-1], a[k - bb] + aa, a[k]))

    # q = int(input())
    # for _ in range(q):
    #     u, l = map(int, input().split())
    #     u -= 1
    #     if u < n2:
    #         print(tab[u][l])
    #     else:
    #         a = [(0, 0)]
    #         while u >= n2:
    #             for i in a[:]:
    #                 if i[0] + vw[u][1] <= l:
    #                     a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
    #             u = (u - 1) // 2
    #         ans = 0
    #         b = tab[u]
    #         for i, j in a:
    #             ans = max(ans, b[l - i] + j)
    #         print(ans)


if __name__ == "__main__":
    main()