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:
# 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)]+[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())
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:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

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 = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = 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()

def merge(before, xw,xv):
    after = [[0,0] for _ in range(len(before))]
    for i,(w,v) in enumerate(after):
        after[i][0] = xw + before[i][0]
        after[i][1] = xv + before[i][1]

    res = []
    i = 0
    j = 0
    while(i < len(before)):
        if(before[i][0] <= after[j][0]):
            res.append(before[i][::])
            i += 1
        else:
            res.append(after[j][::])
            j += 1

    while(j < len(before)):
        res.append(after[j][::])
        j += 1

    return res


# 前処理　最大2**10まで前計算
b_len = min(10, n.bit_length()-1)
n_bef = 2**b_len
bef = [[] for _ in range(n_bef)]
bef[1] = [[0,0],[W[0],V[0]]]
for i in range(2,n_bef):
    bef[i] = merge(bef[i//2], W[i-1], V[i-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
    aft = [[0,0]]
    while(par >= n_bef):
        aft = merge(aft, W[par-1], V[par-1])
        par //= 2

    max_ans = 0
    max_bef_v = 0
    i_bef = 0
    for aw,av in aft[::-1]:
        lim_w = Li - aw
        if(lim_w < 0):
            continue

        while(i_bef < len(bef[par])):
            if(bef[par][i_bef][0] > lim_w):
                break
            max_bef_v = max(max_bef_v,bef[par][i_bef][1])
            i_bef += 1
        max_ans = max(max_ans, av + max_bef_v)

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

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 = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = 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()

def merge(before, xw,xv):
    after = [[0,0] for _ in range(len(before))]
    for i,(w,v) in enumerate(after):
        after[i][0] = xw + before[i][0]
        after[i][1] = xv + before[i][1]

    res = []
    i = 0
    j = 0
    while(i < len(before)):
        if(before[i][0] <= after[j][0]):
            res.append(before[i][::])
            i += 1
        else:
            res.append(after[j][::])
            j += 1

    while(j < len(before)):
        res.append(after[j][::])
        j += 1

    return res


# 前処理　最大2**11まで前計算
b_len = min(12, n.bit_length()-1)
n_bef = 2**b_len
bef = [[] for _ in range(n_bef)]
bef[1] = [[0,0],[W[0],V[0]]]
for i in range(2,n_bef):
    bef[i] = merge(bef[i//2], W[i-1], V[i-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
    aft = [[0,0]]
    while(par >= n_bef):
        aft = merge(aft, W[par-1], V[par-1])
        par //= 2

    max_ans = 0
    max_bef_v = 0
    i_bef = 0
    for aw,av in aft[::-1]:
        lim_w = Li - aw
        if(lim_w < 0):
            continue

        while(i_bef < len(bef[par])):
            if(bef[par][i_bef][0] > lim_w):
                break
            max_bef_v = max(max_bef_v,bef[par][i_bef][1])
            i_bef += 1
        max_ans = max(max_ans, av + max_bef_v)

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

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 = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = 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()

def merge(before, xw,xv):
    after = [[0,0] for _ in range(len(before))]
    for i,(w,v) in enumerate(after):
        after[i][0] = xw + before[i][0]
        after[i][1] = xv + before[i][1]

    res = []
    i = 0
    j = 0
    while(i < len(before)):
        if(before[i][0] <= after[j][0]):
            res.append(before[i][::])
            i += 1
        else:
            res.append(after[j][::])
            j += 1

    while(j < len(before)):
        res.append(after[j][::])
        j += 1

    return res


# 前処理　最大2**11まで前計算
b_len = min(11, n.bit_length()-1)
n_bef = 2**b_len
bef = [[] for _ in range(n_bef)]
bef[1] = [[0,0],[W[0],V[0]]]
for i in range(2,n_bef):
    bef[i] = merge(bef[i//2], W[i-1], V[i-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
    aft = [[0,0]]
    while(par >= n_bef):
        aft = merge(aft, W[par-1], V[par-1])
        par //= 2

    max_ans = 0
    max_bef_v = 0
    i_bef = 0
    for aw,av in aft[::-1]:
        lim_w = Li - aw
        if(lim_w < 0):
            continue

        while(i_bef < len(bef[par])):
            if(bef[par][i_bef][0] > lim_w):
                break
            max_bef_v = max(max_bef_v,bef[par][i_bef][1])
            i_bef += 1
        max_ans = max(max_ans, av + max_bef_v)

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

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)]+[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())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        dv += [vw[u][0]+v1 for v1 in dv]
        dw += [vw[u][1]+w1 for w1 in dw]
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

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)]+[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())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        dv += (vw[u][0]+v1 for v1 in dv)
        dw += (vw[u][1]+w1 for w1 in dw)
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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


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

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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


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

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

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)]+[tuple(map(int,readline().split())) for _ in range(n)]

#print(vw)
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
    #for j in range(1,L):
    #    memo[i][j] = max(memo[i][j],memo[i][j-1])


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

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0
    for w,v in dic:
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 11

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    w_sum = 0
    for state in range(1<<x):
        # 微妙な高速化
        if state&1 and w_sum > l:
            continue
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > l:
                break
        if w_sum > l:
            continue
        res = l-w_sum
        ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    w_sum = 0
    for state in range(1<<x):
        # 微妙な高速化
        if state&1 and w_sum > max_l:
            continue
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > max_l:
                break
        if w_sum > max_l:
            continue
        if ret[w_sum] < v_sum:
            ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 11

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    for state in range(1<<x):
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > l:
                break
        if w_sum > l:
            continue
        res = l-w_sum
        ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    for state in range(1<<x):
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > max_l:
                break
        if w_sum > max_l:
            continue
        if ret[w_sum] < v_sum:
            ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

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


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] = np.array([(0,0), (W[0], V[0])], dtype=np.int32)


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

@njit("i4[:,:],i4,i4", cache=True)
def sub0(l, w, v):
    ll = np.zeros_like(l)
    ll += l
    ll[:,0] += w
    ll[:,1] += v
    s = 1
    nl = np.zeros((l.shape[0]*2, 2), dtype=np.int32)
    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[s,:] = l[i1]
                s += 1
            i1 += 1
        elif i2<length:
            if ll[i2][1]>nl[-1][1]:
                nl[s,:] = ll[i2]
                s += 1
            i2 += 1      
    return nl[:s]

while q:
    u = q.pop()
    l = np.array(d[u], dtype=np.int32)
    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)

@njit("i4[:,:],i4[:,:],i4", cache=True)
def merge(l1, l2, L):
    right = len(l2)-1
    ans = -1
    for left in range(len(l1)):
        w1, v1 = l1[left]
        while right>0 and w1+l2[right][0]>L:
            right -= 1
        if w1+l2[right][0]<=L:
            ans = max(ans, v1+l2[right][1])
        else:
            break
    return ans
@njit("i4,i4,i4[:],i4[:],i4[:,:],i4[:]", cache=True)
def sub(vv, L, W, V, l, b):
    if not b[vv]:
        ll = np.array([(0,0)], dtype=np.int32)
        while not b[vv]:
            ll = sub0(ll, W[vv], V[vv])
        tmp = ll
    else:
        tmp = np.array([(0,0)], dtype=np.int32)
    ans = merge(l, tmp, L)
    return ans
        
q = int(input())
ans = [None]*q
b = np.array([int(item is not None) for item in d], dtype=np.int32)
V = np.array(V, dtype=np.int32)
W = np.array(W, dtype=np.int32)

for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    vv2 = vv
    while d[vv2] is None:
        vv2 = (vv2-1)//2
    ans[i] = sub(vv, ll, W, V, d[vv2], b)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 10

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    for state in range(1<<x):
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > l:
                break
        if w_sum > l:
            continue
        res = l-w_sum
        ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    for state in range(1<<x):
        v_sum = 0
        w_sum = 0
        vi = v
        for j in range(x):
            if state & 1<<j:
                v_sum += vw[vi-1][0]
                w_sum += vw[vi-1][1]
            vi >>= 1
            if w_sum > max_l:
                break
        if w_sum > max_l:
            continue
        if ret[w_sum] < v_sum:
            ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 11

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > max_l:
                    break
            if w_sum > max_l:
                continue
            if ret[w_sum] < v_sum:
                ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 9

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > max_l:
                    break
            if w_sum > max_l:
                continue
            if ret[w_sum] < v_sum:
                ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
vw = [list(map(int, input().split())) for i in range(n)]
q = int(input())
vl = [list(map(int, input().split())) for i in range(q)]

ans = [0]*q

top = set()
mid = set()

m = 10

for v,l in vl:
    if v < 1<<(m-1):
        top.add(v)
    elif v < 1<<m:
        mid.add(v)
    else:
        while 1<<m <= v:
            v //= 2
        mid.add(v)

max_l = 10**5
def knapsack(v,end=0, l=max_l, l_list=[0]*(max_l+1),):
    x = v.bit_length() - end.bit_length()
    ret = 0
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(v):
    x = v.bit_length()
    ret = [0]*(max_l+1)
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            vi = v
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw[vi-1][0]
                    w_sum += vw[vi-1][1]
                vi >>= 1
                if w_sum > max_l:
                    break
            if w_sum > max_l:
                continue
            if ret[w_sum] < v_sum:
                ret[w_sum] = v_sum
    return ret

d = dict()
for v in mid:
    b = knapsack_mid(v)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = b[i]
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        ans[i] = knapsack(v,0,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<m <= vv:
            vv //=2
        ans[i] = knapsack(v, vv, l, l_list=d[vv])

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

Submission status: Time Limit Exceeded

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)]+[tuple(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 9
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
    #for j in range(1,L):
    #    memo[i][j] = max(memo[i][j],memo[i][j-1])


def dfs(v,w,u):
    if u < N:
        return memo[u][l-w]+v if l>w else 0
    else:
        return max(dfs(v,w,u>>1),
                   dfs(v+vw[u][0],w+vw[u][1],u>>1))
        

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