Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

0
3
3

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

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

Sample Input 2

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

Sample Output 2

256
255
250
247
255
259
223
253



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


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs=[]
    ws=[]
    costs=tuple(tuple(map(int, input().split())) for i in range(N))
    visited=[0]*N
    Q=int(input())
    qs= tuple(tuple(map(int, input().split())) for i in range(Q))
    maxL=int(max([qs[i][1] for i in range(Q)]))

    
        
    for v,L in qs:
        if v==1:
            v,w=costs[1]
            if w<=L:print(v)
            else:print(0)
            continue

        n=[]
        while v:
            n.append(costs[v-1])
            v=v//2
        ln=len(n)
        n1=n[:ln//2]
        n2=n[ln//2:]
        
        n1c=[]
        n2c=[]
        for i in range(len(n1)+1):
            for n1b in combinations(n1,i):
                vsum=sum([x[0] for x in n1b])
                wsum=sum([x[1] for x in n1b])
                n1c.append((wsum,vsum))
        for i in range(len(n2)+1):
            for n2b in combinations(n2,i):
                vsum=sum([x[0] for x in n2b])
                wsum=sum([x[1] for x in n2b])
                n2c.append((wsum,vsum))
        vmax=10**5+1
        n1c.sort(key=lambda k: k[0]*vmax+k[1])
        n2c.sort(key=lambda k: k[0]*vmax+k[1])
        
        j1=1
        for i in range(1,len(n1c)):
            if n1c[i][1]>n1c[j1-1][1]:
                n1c[j1]=n1c[i]
                j1+=1
        
        j2=1
        for i in range(1,len(n2c)):
            if n2c[i][1]>n2c[j2-1][1]:
                n2c[j2]=n2c[i]
                j2+=1

        j=j1-1
        ans=0
        for i in range(j2):
            w,v=n2c[i]
            while n1c[j][0]+w>L and j>=0:
                j-=1
            if j==-1:
                break
            ans=max(ans,v+n1c[j][1])
        print(ans)







if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
import numpy as np
def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs=[]
    ws=[]
    costs=tuple(tuple(map(int, input().split())) for i in range(N))
    visited=[0]*N
    Q=int(input())
    qs= tuple(tuple(map(int, input().split())) for i in range(Q))
    maxL=int(max([qs[i][1] for i in range(Q)]))

    
        
    for v,L in qs:
        if v==1:
            v,w=costs[1]
            if w<=L:print(v)
            else:print(0)
            continue

        n=[]
        while v:
            n.append(costs[v-1])
            v=v//2
        ln=len(n)
        n1=n[:ln//2]
        n2=n[ln//2:]
        
        n1c=[]
        n2c=[]
        for i in range(len(n1)+1):
            for n1b in combinations(n1,i):
                vsum=sum([x[0] for x in n1b])
                wsum=sum([x[1] for x in n1b])
                n1c.append((wsum,vsum))
        for i in range(len(n2)+1):
            for n2b in combinations(n2,i):
                vsum=sum([x[0] for x in n2b])
                wsum=sum([x[1] for x in n2b])
                n2c.append((wsum,vsum))
        vmax=10**5+1
        n1c.sort(key=lambda k: k[0]*vmax+k[1])
        n2c.sort(key=lambda k: k[0]*vmax+k[1])
        
        j1=1
        for i in range(1,len(n1c)):
            if n1c[i][1]>n1c[j1-1][1]:
                n1c[j1]=n1c[i]
                j1+=1
        
        j2=1
        for i in range(1,len(n2c)):
            if n2c[i][1]>n2c[j2-1][1]:
                n2c[j2]=n2c[i]
                j2+=1

        j=j1-1
        ans=0
        for i in range(j2):
            w,v=n2c[i]
            while n1c[j][0]+w>L and j>=0:
                j-=1
            if j==-1:
                break
            ans=max(ans,v+n1c[j][1])
        print(ans)







if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, Q;

vector<pair<ll, ll> > tree;
vector<pair<ll, ll> > que;
vector<vector<ll> > best_per_weight;
int max_idx = 1;
ll max_l;

ll brute_force(int v, ll w, ll acc_val, ll max_wq)
{  
    if (v < max_idx)
    {
        return best_per_weight[v][max_wq - w] + acc_val;
    }
    else
    {
        ll c_value = tree[v].first;
        ll c_weight = tree[v].second;
        int parent = (v-1)/2;

        ll not_pick = brute_force(parent, w, acc_val, max_wq);

        ll pick;
        if (c_weight + w > max_wq) return not_pick;
        else 
        {
            pick = brute_force(parent, c_weight + w, acc_val + c_value, max_wq);
        }

        return pick > not_pick ? pick : not_pick;
    }
    

}

int main()
{

    cin >> N;
    for(int i = 0; i < N; i++)
    {
        ll v,w;
        cin >> v >> w;
        tree.push_back(make_pair(v,w));
    }

    cin >> Q;
    max_l = 0;
    for(int i = 0; i < Q; i++)
    {
        ll v, l;
        cin >> v >> l;
        que.push_back(make_pair(v-1,l));
        if (max_l < l) max_l = l;
    }

    max_idx = 1024 > N ? N : 1024;

    for (int i = 0; i < max_idx; i++) 
    {
        // vector<ll> b_val(max_l+1, 0);
        vector<ll> b_val;
        if (i == 0)
        {
            ll c_value = tree[i].first;
            ll c_weight = tree[i].second;
            if (c_weight <= max_l) 
            {
                for (int k = 0; k < c_weight; k++)
                {
                    b_val.push_back(0);
                }
                for (int k = c_weight; k < max_l+1; k++)
                {
                    b_val.push_back(c_value);
                }
            }
        }
        else
        {
            ll c_value = tree[i].first;
            ll c_weight = tree[i].second;
            for (int j = 0; j < max_l + 1; j++)
            {
                int parent = (i - 1) / 2;
                int prev_idx = j - c_weight;
                if (prev_idx < 0) b_val.push_back(best_per_weight[parent][j]);
                else 
                {
                    ll tmp = best_per_weight[parent][prev_idx] + c_value;
                    tmp = tmp > best_per_weight[parent][j] ? tmp : best_per_weight[parent][j];
                    b_val.push_back(tmp);
                }
            }
        }
        best_per_weight.push_back(b_val);
    }
// 
    // cout << "FInish" << endl;

    for (auto q : que)
    {
        int v = q.first;
        int L = q.second;
        ll best_val = brute_force(v, 0, 0, L);
        cout << best_val << endl;
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

if K > 50:
    print(" ".join([str(N) for i in range(N)]))
    sys.exit()

for i in range(K):
    A_new = [0 for i in range(N)]
    imos_table = [0 for i in range(N)]

    for j in range(N): # ここで一度状態の差分についてをimos_tableに保存
        left = max(0, j - A[j])
        right = j + A[j] + 1
        imos_table[left] += 1
        if right >= N:
            pass
        else:
            imos_table[right] -= 1
    
    # tmp を使って前から順に状態を計算していく
    tmp = 0
    for j in range(N):
        tmp += imos_table[j]
        A_new[j] += tmp

    A = copy.deepcopy(A_new)

print(" ".join(map(str, A)))

Submission status: Runtime Error

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] = [(0,0), (W[0], V[0])]

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

@njit("i4[:,:],i4,i4")
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")
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

def sub(vv, L):
    if d[vv] is None:
        ll = np.array([(0,0)], dtype=np.int32)
        while d[vv] is None:
            ll = sub0(ll, W[vv], V[vv])
            vv = (vv-1)//2
        tmp = ll
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = merge(l, np.array(tmp, dtype=np.int32), L)
    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: Runtime Error

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

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 tmp > 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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
lm = 10**5+1
h = min(n+1,1<<10)
l = [list(map(int,input().split())) for i in range(n)]
dp = [None]*h
dp[0] = [0]*lm

for i in range(1,h):
    v,w = l[i-1]
    p = i//2
    d = dp[p][:]
    
    for j in range(lm-1,w-1,-1):
        d[j] = max(d[j],d[j-w]+v)
    
    dp[i] = d

q = int(input())
for _ in range(q):
    v,m = map(int,input().split())
    if v < h:
        print(dp[v][m])
    else:
        vv = []
        ww = []
        while v >= h:
            vv.append(l[v][0])
            ww.append(l[v][1])
            v >>= 1
        ans = dp[v][m]
        le = len(vv)
        V = [0]*(1<<le)
        W = [0]*(1<<le)
        for i in range(1,1<<le):
            ind = i&(-i)
            indd = ind.bit_length()-1
            wi = W[i-ind] + ww[indd]
            W[i] = wi
            if wi <= m:
                vi = V[i-ind]+vv[indd]
                V[i] = vi
                ans = max(ans,vi+dp[v][m-wi])
        print(ans)

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        V.append(v)
        W.append(w)
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v-1][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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v-1][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
lm = 10**5+1
h = min(n,1<<10)+1
l = [list(map(int,input().split())) for i in range(n)]
dp = [None]*h
dp[0] = [0]*lm

for i in range(1,h):
    v,w = l[i-1]
    p = i//2
    d = dp[p][:]
    
    for j in range(lm-1,w-1,-1):
        d[j] = max(d[j],d[j-w]+v)
    
    dp[i] = d

q = int(input())
for _ in range(q):
    v,m = map(int,input().split())
    if v < h:
        print(dp[v][m])
    else:
        vv = []
        ww = []
        while v >= h:
            vv.append(l[v][0])
            ww.append(l[v][1])
            v >>= 1
        ans = dp[v][m]
        le = len(vv)
        V = [0]*(1<<le)
        W = [0]*(1<<le)
        for i in range(1,1<<le):
            ind = i&(-i)
            indd = ind.bit_length()-1
            wi = W[i-ind] + ww[indd]
            W[i] = wi
            if wi <= m:
                vi = V[i-ind]+vv[indd]
                V[i] = vi
                ans = max(ans,vi+dp[v][m-wi])
        print(ans)

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        V.append(v)
        W.append(w)
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
lm = 10**5+1
h = min(n,1<<11)+1
l = [list(map(int,input().split())) for i in range(n)]
dp = [None]*h
dp[0] = [0]*lm

for i in range(1,h):
    v,w = l[i-1]
    p = i//2
    d = dp[p][:]
    
    for j in range(lm-1,w-1,-1):
        d[j] = max(d[j],d[j-w]+v)
    
    dp[i] = d

q = int(input())
for _ in range(q):
    v,m = map(int,input().split())
    if v < h:
        print(dp[v][m])
    else:
        vv = []
        ww = []
        while v >= h:
            vv.append(l[v][0])
            ww.append(l[v][1])
            v >>= 1
        ans = dp[v][m]
        le = len(vv)
        V = [0]*(1<<le)
        W = [0]*(1<<le)
        for i in range(1,1<<le):
            ind = i&(-i)
            indd = ind.bit_length()-1
            wi = W[i-ind] + ww[indd]
            W[i] = wi
            if wi <= m:
                vi = V[i-ind]+vv[indd]
                V[i] = vi
                ans = max(ans,vi+dp[v][m-wi])
        print(ans)

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
            V.append(v)
            W.append(w)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp[half][j - w] + v:
                    dp_[j] = dp[half][j - w] + v
            dp.append(dp_)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(maxL+1):
                if j < w:
                    dp_[j] = dp[half][j]
                else:
                    dp_[j] = max(dp[half][j], dp[half][j - w] + v)
            dp.append(dp_)
        else:
            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
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = LI()
        if i > n:
            V.append(v)
            W.append(w)
            continue
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        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
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp-1][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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp-1][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = LI()
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        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
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp-1][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_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp-1][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()