Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

0
3
3

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

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

Sample Input 2

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

Sample Output 2

256
255
250
247
255
259
223
253



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


Sample output:
0
3
3

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    N = int(readline())
    VW = [list(map(int, readline().split())) for i in range(N)]
    Q = int(readline())
    vL = [list(map(int, readline().split())) for i in range(Q)]

    mem = {}

    for v, L in vL:
        print(rec(v-1, L, VW, mem))

def rec(n, cap, VW, mem):
    p = (n, cap)
    if p in mem:
        return mem[p]
    
    v, w = VW[n]
    if n == 0:
        if cap >= w:
            return v
        else:
            return 0

    parent = (n - 1) // 2
    ret = max(
        rec(parent, cap, VW, mem),
        (rec(parent, cap - w, VW, mem) + v) if cap - w >= 0 else 0
    )
    
    mem[p] = ret
    return ret

solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
n=int(input())

map1=[]
for _ in range(n):
    vn,w=map(int,input().split())
    map1.append((vn,w))
def main():
    q=int(input())
    for _ in range(q):
        v,l=map(int,input().split())
        length=v.bit_length()
        dd = defaultdict(int)
        dd[0] = 0
        while v:
            for tw, tv in list(dd.items()):
                a,b=map1[v-1]
                if tw + b <= l:
                    dd[tw + b] = max(tv + a, dd[tw + b])
            v//=2
        print(max(dd.values()))
        #print(dd)     

main()

Submission status: Time Limit Exceeded

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

N = int(input())
VW = [list(map(int, input().split())) for n in range(N)]
Q = int(input())
vL = [list(map(int, input().split())) for q in range(Q)]

def query(v, L):
  vlist = []
  while v > 0:
    vlist.append(v)
    v = v // 2
  dp = [[0] * (L+1) for l in range(len(vlist) + 1)]
  for k in range(len(vlist)):
    for l in range(L+1):
      if l < VW[vlist[k]-1][1]:
        dp[k+1][l] = dp[k][l]
      else:
        dp[k+1][l] = max(dp[k][l], dp[k][l-VW[vlist[k]-1][1]] + VW[vlist[k]-1][0])
  print(dp[len(vlist)][L])


for v, L in vL:
  query(v, L)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


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

    NN = 1 << 18
    Lmax = 10**5
    N = int(input())
    V = [0] * (NN+1)
    W = [0] * (NN+1)
    for i in range(1, N+1):
        v, w = map(int, input().split())
        V[i] = v
        W[i] = w

    V_list = [[] for _ in range(NN+1)]
    W_list = [[] for _ in range(NN+1)]
    for i in range(1, NN):
        p = i // 2
        for v in V_list[p]:
            V_list[i].append(v)
        for w in W_list[p]:
            W_list[i].append(w)
        V_list[i].append(V[i])
        W_list[i].append(W[i])
    dp_upper = [[0] * (Lmax + 1) for _ in range(1 << 9)]
    for i in range(1, 1 << 9):
        K = len(V_list[i])
        for j in range(1 << K):
            vs = 0
            ws = 0
            for k in range(K):
                if j >> k & 1:
                    vs += V_list[i][k]
                    ws += W_list[i][k]
            if ws <= Lmax:
                dp_upper[i][ws] = max(dp_upper[i][ws], vs)
        for w in range(1, Lmax+1):
            dp_upper[i][w] = max(dp_upper[i][w], dp_upper[i][w-1])
    par = [0] * (NN+1)
    for i in range(1 << 9, NN):
        p = i // 2
        if par[p] == 0:
            par[i] = p
        else:
            par[i] = par[p]

    for _ in range(int(input())):
        v, L = map(int, input().split())
        if v < 512:
            print(dp_upper[v][L])
        else:
            p = par[v]
            K = len(V_list[v]) - 9
            VW_list = []
            for j in range(1<<K):
                vs = 0
                ws = 0
                for k in range(K):
                    if j >> k & 1:
                        vs += V_list[v][k+9]
                        ws += W_list[v][k+9]
                if ws <= L:
                    VW_list.append((vs, ws))
            ans = 0
            for vv, ww in VW_list:
                ans = max(ans, vv + dp_upper[p][L - ww])
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
VW = tuple(tuple(map(int, input().split())) for _ in range(N))
q = int(input())

def f(x, W):
    S = []
    b = x.bit_length()
    for j in range(b):
        S.append(VW[(x>>j)-1])
    def make(S):
        T = {0: 0}
        for v, w in S:
            # 価値v, 重さw
            T0 = dict(T)
            for k, val in T.items():
                if k+w > W:
                    continue
                if k+w in T0:
                    T0[k+w] = max(T0[k+w], val + v)
                else:
                    T0[k+w] = val + v
            T = T0
        v = 0
        R = []
        for k in sorted(T):
            v = max(v, T[k])
            # (重さk, 重さk以下での価値の最大v)
            R.append((k, v))
        return R

    def solve(T0, T1):
        T0.sort()
        T1.sort(reverse=1)

        it = iter(T1); k1, v1 = next(it)
        yield 0
        for k0, v0 in T0:
            # 重さの和がW以下になるようにスライドする
            while k0 + k1 > W:
                k1, v1 = next(it)
            yield v0 + v1

    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(S[:N//2])
    T1 = make(S[N//2:])

    # 2つの全列挙を元に解を求める
    return max(solve(T0, T1))

for _ in range(q):
  x, l = map(int, input().split())
  ans = f(x, l)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
map1=[]
for _ in range(n):
    vn,w=map(int,input().split())
    map1.append((vn,w))
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))

q=int(input())
for _ in range(q):
    v,l=map(int,input().split())
    length=v.bit_length()
    dd = defaultdict(int)
    dd[0] = 0
    while v:
        for tw, tv in list(dd.items()):
            a,b=map1[v-1]
            if tw + b <= l:
                dd[tw + b] = max(tv + a, dd[tw + b])
        v//=2
    print(max(dd.values()))
    #print(dd)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
vw = []
for _ in range(n):
  vw.append([int(i) for i in input().split()])

q = int(input())
vl = []
for _ in range(q):
  vl.append([int(i) for i in input().split()])

def knapsack(i, w):
    if i>=len(items):
        return 0
    elif  w - items[i][1] < 0.0:
        return knapsack(i+1, w)
    else:
        p1 = knapsack(i+1, w)
        p2 = knapsack(i+1, w - items[i][1]) + items[i][0]
        if p1>p2:
            return p1
        else:
            return p2

for li in vl:
  index = li[0]
  items = []
  while index > 0:
    items.append(vw[index - 1])
    index = index // 2
    
  print(knapsack(0, li[1]))

Submission status: Accepted

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

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

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    while temp and temp[-1][1]>10**5:
        temp.pop()
    m=len(temp)
    for i in range(1,m):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(m-1):
        L=temp[i][1]
        R=temp[i+1][1]
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        for j in range(L,10**5+1):
            dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])

Submission status: Accepted

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

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

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Accepted

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

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            if Aw[jdx] + w > limit:
                break
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1

    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N or Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw


limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<12)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
            Rv[i].append(vm)
            Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    ctr = 0
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ctr = max(ctr, kv+Rv[v][cnt])
    ans[i] = ctr

print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            if Aw[jdx] + w > limit:
                break
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1

    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N or Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw


limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<11)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
            Rv[i].append(vm)
            Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    ctr = 0
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ctr = max(ctr, kv+Rv[v][cnt])
    ans[i] = ctr

print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
n =int(input())
vw = [(0,0)]  
for _ in range(n):
    vw.append(list(map(int,input().split())))

A  =10
N = min(1<<A,n+1)
memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q = int(input())
ans_ = [0]*q
for _ in range(q):
    u,l = map(int,input().split())
 
    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            val = memo[u][l-w] + v
            if val > ans: ans = val
    ans_[_] = ans
print(*ans_,sep="\n")

Submission status: Accepted

Solution code:
import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q, = map(int,readline().split())
ans_ = [0]*q
for _ in range(q):
    u,l = map(int,readline().split())

    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            val = memo[u][l-w] + v
            if val > ans: ans = val
    ans_[_] = ans
    
print(*ans_,sep="\n")

Submission status: Accepted

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

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 12
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 11
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)

Submission status: Accepted

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

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

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
from numba import njit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:],i4[:])',cache=True)
def precompute(n,v,w):
    dp = np.zeros((1024,10**5+1),np.int32)
    for i in range(1,min(1024,n+1)):
        vi = v[i]
        wi = w[i]
        p = i//2
        dp[i]=dp[p]
        for j in range(wi,10**5+1):
            dp[i][j] = max(dp[i][j],dp[p][j-wi]+vi)
    return dp

@njit('(i4,i4[:],i4[:],i4[:],i4[:])',cache=True)
def main(n,v,w,vq,lq):
    dp = precompute(n,v,w)
    values = np.empty(1024,np.int32)
    weights = np.empty(1024,np.int32)

    def solve(V,L,values,weights,dp):
        if V < 1024:
            return dp[V][L]
        values[0] = 0
        weights[0] = 0
        p = 0
        while V >= 1024:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j]+ v[V]
                weights[j + (1 << p)] = weights[j] + w[V]
            p += 1
            V >>= 1
        ans = 0
        for i in range(1 << p):
            if weights[i] <= L:
                x = dp[V][L-weights[i]] + values[i]
                ans = max(ans,x)
        return ans
    q = len(vq)
    for i in range(q):
        x = solve(vq[i],lq[i],values,weights,dp)
        print(x)
       
n = int(readline())
stdin = np.array(read().split(),np.int32)
v = np.zeros(n+1,np.int32)
w = np.zeros(n+1,np.int32)
v[1:] = stdin[:2*n:2]
w[1:] = stdin[1:2*n:2]
query = stdin[2*n+1:]
vq = query[::2]
lq = query[1::2]

main(n,v,w,vq,lq)

Submission status: Accepted

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


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


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


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

    dp = [[] for _ in range(2048)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N + 1, 2048)):
        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:
        a = [(0, 0)]
        while n >= 2048:
            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()