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
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
M = 10 ** 5 + 1
K = 12
A = [(0, 0)] * max(N + 1, 1 << K)
X = [[], [-1] * M]
X[1][0] = 0
v, w = map(int, input().split())
X[1][w] = v
A[1] = (v, w)
for i in range(2, min(N + 1, 1 << K)):
    v, w = map(int, input().split())
    if i % 2 == 0:
        X.append(X[i // 2][:])
    else:
        X.append([])
        X[i] = X[i // 2]
    
    for j in range(w, M)[::-1]:
        if X[i][j-w] >= 0:
            X[i][j] = max(X[i][j], X[i][j-w] + v)
    
    A[i] = (v, w)

for i in range(1 << K, N + 1):
    v, w = map(int, input().split())
    A[i] = (v, w)

if len(X) < 1 << K:
    for i in range(len(X), 1 << K):
        X.append([-1] * M)

for i in range(1 << K - 1, 1 << K):
    for j in range(1, M):
        X[i][j] = max(X[i][j], X[i][j-1])

Q = int(input())
for _ in range(Q):
    i, maw = map(int, input().split())
    if i < 1 << K - 1:
        V = []
        W = []
        while i:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        k = len(V)
        ma = 0
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, vv)
        print(ma)
    else:
        V = []
        W = []
        while i >= 1 << K:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        k = len(V)
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        ma = X[ii][maw]
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
M = 10 ** 5 + 1
K = 11
A = [(0, 0)] * max(N + 1, 1 << K)
X = [[], [-1] * M]
X[1][0] = 0
v, w = map(int, input().split())
X[1][w] = v
A[1] = (v, w)
for i in range(2, min(N + 1, 1 << K)):
    v, w = map(int, input().split())
    if i % 2 == 0:
        X.append(X[i // 2][:])
    else:
        X.append([])
        X[i] = X[i // 2]
    
    for j in range(w, M)[::-1]:
        if X[i][j-w] >= 0:
            X[i][j] = max(X[i][j], X[i][j-w] + v)
    
    A[i] = (v, w)

for i in range(1 << K, N + 1):
    v, w = map(int, input().split())
    A[i] = (v, w)

if len(X) < 1 << K:
    for i in range(len(X), 1 << K):
        X.append([-1] * M)

for i in range(1 << K - 1, 1 << K):
    for j in range(1, M):
        X[i][j] = max(X[i][j], X[i][j-1])

Q = int(input())
for _ in range(Q):
    i, maw = map(int, input().split())
    if i < 1 << K - 1:
        V = []
        W = []
        while i:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        k = len(V)
        ma = 0
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, vv)
        print(ma)
    else:
        V = []
        W = []
        while i >= 1 << K:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        k = len(V)
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        ma = X[ii][maw]
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 10
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))
  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    lnap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = lnap
      if i and wn >= ls[i-1][1] and vn <= ls[i-1][0]:
        continue
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Time Limit Exceeded

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

    N = int(input())
    half = min(2 ** 10, N)

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

    MAX_W = 10 ** 5 + 1

    dp = [[0] * (MAX_W) for _ in range(half + 1)]

    for i in range(1, half + 1):
        V, W = VW[i - 1][0], VW[i - 1][1]
        for j in range(W):
            dp[i][j] = dp[i // 2][j]
        for j in range(W, MAX_W):
            dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)


    def calc(n, L):
        ans = 0
        lst = []
        lst_append = lst.append
        while n > half:
            lst_append(n)
            n //= 2
        # print (lst)
        length = len(lst)
        for i in range(2 ** length):
            v = 0
            w = 0
            for j in range(length):
                if ((i >> j) & 1):
                    v += VW[lst[j] - 1][0]
                    w += VW[lst[j] - 1][1]
            if L >= w:
                ans = max(ans, dp[n][L - w] + v) 
        return ans

    Q = int(input())
    for _ in range(Q):
        v, L = map(int, input().split())
        if v > half:
            print (calc(v, L))
        else: #こっち側はOK(当然)
            print (dp[v][L])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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#累積和
#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)]))

    dps=dict()
    dp=np.zeros(maxL+1,dtype='i4')
    v,w=costs[0]

    #print(dp[w:maxL+1])
    if w<=maxL:
        #print(w,maxL+1,maxL+1-w)        
        dp[w:maxL+1]=np.maximum(dp[0:maxL+1-w]+v,dp[w:maxL+1])

    dps[1]=dp
    visited[0]=1
    #@lru_cache(maxsize = None)
    #import numba
    #@numba.jit(nopython=True)
    def r(n,dpo):
        dpn=np.copy(dpo)
        v,w=costs[n-1]
        #if n==4:
            #print(par)
            #print(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        if w<=maxL:
            dpn[w:maxL+1]=np.maximum(dpn[0:maxL+1-w]+v,dpn[w:maxL+1])
        dps[n]=dpn
        return dpn
        
    for v,L in qs:
        q=deque()
        while v:
            if v in dps:
                dp=dps[v]
                break
            else:
                q.append(v)
                v=v//2
        #print(dp)
        while q:
            v=q.pop()
            dp=r(v,dp)

            
            

        print(dp[L])
        #print(dp)
    
    #print(dps[8])
        
        


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def make(A, v):
    T = []
    while v != 0:
        T.append(A[v - 1])
        v //= 2

    M = len(T)
    K = []
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]
            if W > 10 ** 5 + 10:
                break
        
        if W < 10 ** 5 + 10:
            K.append((W, V))
    
    K.sort(key=lambda l: (l[0], -l[1]))

    W2 = [0]
    V2 = [0]
    mv = 0
    for w, v in K:
        if v <= mv:
            continue

        mv = v
        W2.append(w)
        V2.append(mv)

    return (tuple(W2), tuple(V2))

@lru_cache(maxsize=None)
def f(A, v, L):
    T = []
    while v != 0:
        T.append(A[v - 1])
        v //= 2

    M = len(T)
    res = 0
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]

        if W <= L:
            res = max(res, V)

    return res


P = 8
@lru_cache(maxsize=None)
def f2(A, v, L, V2, W2):
    T = []
    while v >= 2 ** P:
        T.append(A[v - 1])
        v = v >> 1

    M = len(T)
    res = 0
    for k in range(2 ** M):
        V = 0
        W = 0
        for i in range(M):
            if (k >> i) & 1:
                V += T[i][0]
                W += T[i][1]
            if W > L:
                break

        R = L - W
        t = bisect.bisect_right(W2, R)
        res = max(res, V + V2[min(t, len(W2)) - 1])

    return res


def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(tuple(read_values()))
    A = tuple(A)
    K = dict()
    Q = int(input())
    ans = [""] * Q
    for q in range(Q):
        v, L = read_values()
        if v.bit_length() <= P:
            ans[q] = str(f(A, v, L))
        else:
            b = v.bit_length()
            v2 = v >> (b - P)
            K2 = K.setdefault(v2, make(A, v2))
            ans[q] = str(f2(A, v, L, K2[1], K2[0]))

    print("\n".join(ans))
    

if __name__ == "__main__":
    main()

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

#print(vw)
A = 9
N = min(1<<A,n+1)
"""
memo = [[(0,0)] for _ in range(N)]


memo[1].append((vw[1][1],vw[1][0]))

for i in range(2,N):
    v,w = vw[i]
    m2 = [(w+w1,v+v1) for w1,v1 in memo[i>>1]]
    
    idx = 0
    L = len(m2)
    for (w,v) in memo[i>>1][1:]:
        while m2[idx][0] < w and idx < L:
            w2,v2 = m2[idx]
            memo[i].append((w2,max(v2,memo[i][-1][1])))
            idx += 1
        memo[i].append((w,max(v,memo[i][-1][1])))
    for w,v in m2[idx:]:
        memo[i].append((w,max(v,memo[i][-1][1])))
        
#print(memo)

    #memo[i] = memo[i>>1] + [(w+w1,v+v1) for w1,v1 in memo[i>>1]]

#print(memo)
"""

"""
for i in range(1,N):
    memo[i].sort()
    L = len(memo[i])
    for j in range(1,L):
        I,J = memo[i][j]
        if J >= memo[i][j-1][1]:
            memo[i][j] = (I,J)
"""    
        
from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    #print(lst)
    for w,v in dic:
        idx = bisect_left(lst, (l+1-w,0))-1
        if idx >= 0 and v+lst[idx][1] > ans:
            ans = v+lst[idx][1]
    print(ans)        




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
    

    dic2 = [(0,0)]
    while u:
        
        memo = [(0,0)]
        m2 = [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic2]
        idx = 0
        L = len(m2)
        for (w,v) in dic2[1:]:
            while m2[idx][0] < w and idx < L:
                w2,v2 = m2[idx]
                memo.append((w2,max(v2,memo[-1][1])))
                idx += 1
            memo.append((w,max(v,memo[-1][1])))
        for w,v in m2[idx:]:
            memo.append((w,max(v,memo[-1][1])))
        
        dic2 = memo
        u >>= 1
        
    solve(dic2,dic,l)

Submission status: Time Limit Exceeded

Solution code:
up = lambda x: x//2
ed = 2**10
n = int(input())
itm = []
for _ in range(n):
   v,w = [int(i) for i in input().split()]
   itm.append((v,w))
dplen = min(n,ed)
dp = [ [0]*(10**5+2) for i in range(dplen+1)]
for i in range(1,dplen+1):
   for j in range(10**5+2):
      dp[i][j] = max(dp[up(i)][j], dp[i][max(0,j-1)])
      if (j >= itm[i-1][1]):
         dp[i][j] = max(dp[i][j], dp[up(i)][j-itm[i-1][1]] + itm[i-1][0])
q = int(input())
#print(dp[3][:10])
for i in range(q):
   vrt, l = [int(i) for i in input().split()]
   if vrt <= ed:
      print(dp[vrt][l])
      continue
   koho = []
   y = vrt
   for i in range(10):
      if y <= 2**8:
        break
      koho.append(y)
      y = up(y)
   bn = len(koho)
   mb = 2**bn
   ans = 0
   for j in range(mb):
      curv,curw = 0,0
      for k in range(bn):
         if (j >> k) & 1 :
            curv += itm[koho[k]-1][0]
            curw += itm[koho[k]-1][1]
      if curw <= l:
         curv += dp[vrt][l-curw]
         ans = max(curv)
   print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from bisect import bisect_right

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = []

for _ in range(n):
    v, w = map(int, input().split())
    a.append((v, w))

dp = [{} for _ in range(2**18)]
dp[1][a[0][1]] = a[0][0]

for i in range(2, n+1):
    dp[i].update(dp[i//2])
    for w, v in dp[i//2].items():
        if w + a[i-1][1] in dp[i//2]:
            dp[i][w + a[i-1][1]] = max(dp[i//2][w + a[i-1][1]],
                                       dp[i//2][w] + a[i-1][0])
        else:
            dp[i][w + a[i-1][1]] = dp[i//2][w] + a[i-1][0]

    if a[i-1][1] in dp[i//2]:
        dp[i][a[i-1][1]] = max(dp[i//2][a[i-1][1]], a[i-1][0])
    else:
        dp[i][a[i-1][1]] = a[i-1][0]

q = int(input())
for _ in range(q):
    v, L = map(int, input().split())
    itm = sorted(list(dp[v].items()), key=lambda x: x[0])
    res = sorted(list(dp[v].keys()))
    x = bisect_right(res, L)
    if x != 0:
        ans = -1
        for i in range(x):
            ans = max(ans, itm[i][1])
        print(ans)
    else:
        print(0)

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

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

def get_parents(node,end=0):
    a = []
    while node > end:
        a.append(vw[node-1])
        node //= 2
    return a

max_l = 10**5
def knapsack(vw_list, l, l_list=[0]*(max_l+1),):
    x = len(vw_list)
    ret = 0
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw_list[j][0]
                    w_sum += vw_list[j][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(vw_list):
    x = len(vw_list)
    ret = [0]*(max_l+1)
    for i in range(x):
        for state in range(1<<x):
            v_sum = 0
            w_sum = 0
            for j in range(x):
                if state & 1<<j:
                    v_sum += vw_list[j][0]
                    w_sum += vw_list[j][1]
                if w_sum > max_l:
                    break
            if w_sum > max_l:
                continue
            if ret[w_sum] < v_sum:
                ret[w_sum] = v_sum
            #ret[w_sum] = max(ret[w_sum], v_sum)
    return ret

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

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

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

Submission status: Time Limit Exceeded

Solution code:
up = lambda x: x//2
n = int(input())
itm = []
for _ in range(n):
   v,w = [int(i) for i in input().split()]
   itm.append((v,w))
dplen = min(n,2**8)
dp = [ [0]*(10**5+2) for i in range(dplen+1)]
for i in range(1,dplen+1):
   for j in range(10**5+2):
      dp[i][j] = max(dp[up(i)][j], dp[i][max(0,j-1)])
      if (j >= itm[i-1][1]):
         dp[i][j] = max(dp[i][j], dp[up(i)][j-itm[i-1][1]] + itm[i-1][0])
q = int(input())
#print(dp[3][:10])
for i in range(q):
   vrt, l = [int(i) for i in input().split()]
   if vrt <= 2**8:
      print(dp[vrt][l])
      continue
   koho = []
   y = vrt
   for i in range(10):
      if y <= 2**8:
        break
      koho.append(y)
      y = up(y)
   bn = len(koho)
   mb = 2**bn
   ans = 0
   for j in range(mb):
      curv,curw = 0,0
      for k in range(bn):
         if (j >> k) & 1 :
            curv += itm[koho[k]-1][0]
            curw += itm[koho[k]-1][1]
      if curw <= l:
         curv += dp[vrt][l-curw]
         ans = max(curv)
   print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 12
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))
  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    lnap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = lnap
      if i and wn >= ls[i-1][1] and vn <= ls[i-1][0]:
        continue
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

def knapsack(W,wt,val,n): 
	K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
	for i in range(1,n+1): 
		for w in range(1,W+1): 
			if wt[i] <= w: 
				K[i][w] = max(val[i] + K[i//2][w-wt[i]], K[i//2][w]) 
			else: 
				K[i][w] = K[i//2][w] 
	return K

n = inp()
v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1,n+1):
    v[i],w[i] = ip()
q = inp()
Q = []
mx = 0
for _ in range(q):
    i,L = ip()
    Q.append([i,L])
    mx = max(mx,L)
K = knapsack(mx,w,v,n)
for i in Q:
    ver,L = i
    print(K[ver][L])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return x

N = int(input())
VW = int_mtx(N)
Q = int(input())
vL = int_mtx(Q)

for i in range(Q):
    v = vL[i][0]
    L = vL[i][1]
    Node = []
    while True:
        Node.append(v)
        if v == 1:
            break
        v = int(v/2)

    dp = [0]*(L+1)
    for n in range(1,len(Node)+1):
        V = VW[Node[n-1]-1][0]
        W = VW[Node[n-1]-1][1]
        dp[W:] = [max(x,y) for (x,y) in zip([z+V for z in dp[:-W]],dp[W:])]
#        np.maximum(dp[:-W]+V, dp[W:], out=dp[W:])

    print(int(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections
import bisect

DP = {}
DP[0] = [0 for i in range(100010)]
#DP = [[0 for i in range(100010)] for i in range(2**18 + 1)]

# O(n * max_w)


def napsack(ances_list, values, weights, max_w):
    n = len(weights)
    #print(ances_list, weights, values, max_w)
    for i in range(n):
        if ances_list[i + 1] not in DP:
            DP[ances_list[i + 1]] = [0]
        for w in range(len(DP[ances_list[i + 1]]), max_w + 1):
            if(w >= weights[i]):
                DP[ances_list[i + 1]].append(max(DP[ances_list[i]][w], DP[ances_list[i]][w - weights[i]] + values[i]))
            else:
                DP[ances_list[i + 1]].append(DP[ances_list[i]][w])
            #print(DP[ances_list[i + 1]])
    #print(ances_list, max_w)
    return DP[ances_list[n]][max_w]


N = int(input())
V = [0]
W = [0]
for i in range(N):
    tmpv, tmpw = map(int, input().split())
    V.append(tmpv)
    W.append(tmpw)
Q = int(input())
v = []
L = []
for i in range(Q):
    tmpv, tmpl = map(int, input().split())
    ancesv = []
    ancesw = []
    ances_list = []
    while(tmpv >= 1):
        ancesv.append(V[tmpv])
        ancesw.append(W[tmpv])
        ances_list.append(tmpv)
        tmpv = tmpv // 2
    ances_list.append(0)
    ancesv.reverse()
    ancesw.reverse()
    ances_list.reverse()
    print(napsack(ances_list, ancesv, ancesw, tmpl))

Submission status: Time Limit Exceeded

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

N = int(input())
VW = [list(map(int,input().split())) for _ in range (N)]
Q = int(input())
for _ in range(Q):
    v,L = map(int,input().split())
    A = []
    cur = v
    while cur>0:
        A.append(VW[cur-1])
        cur >>= 1
    M = len(A)
    ans = 0
    for i in range(1<<M):
        res = 0
        wei = 0
        j = 0
        while i>0:
            if i&1:
                res += A[j][0]
                wei += A[j][1]
                if wei>L:
                    break
            i>>=1
            j +=1
        if wei<=L:
            ans = max(res, ans)
    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]]+[list(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 9
N = min(1<<A,n+1)
"""
memo = [[(0,0)] for _ in range(N)]


memo[1].append((vw[1][1],vw[1][0]))

for i in range(2,N):
    v,w = vw[i]
    m2 = [(w+w1,v+v1) for w1,v1 in memo[i>>1]]
    
    idx = 0
    L = len(m2)
    for (w,v) in memo[i>>1][1:]:
        while m2[idx][0] < w and idx < L:
            w2,v2 = m2[idx]
            memo[i].append((w2,max(v2,memo[i][-1][1])))
            idx += 1
        memo[i].append((w,max(v,memo[i][-1][1])))
    for w,v in m2[idx:]:
        memo[i].append((w,max(v,memo[i][-1][1])))
        
#print(memo)

    #memo[i] = memo[i>>1] + [(w+w1,v+v1) for w1,v1 in memo[i>>1]]

#print(memo)
"""

"""
for i in range(1,N):
    memo[i].sort()
    L = len(memo[i])
    for j in range(1,L):
        I,J = memo[i][j]
        if J >= memo[i][j-1][1]:
            memo[i][j] = (I,J)
"""    
        
from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    #print(lst)
    for w,v in dic:
        idx = bisect_left(lst, (l+1-w,0))-1
        if idx >= 0 and v+lst[idx][1] > ans:
            ans = v+lst[idx][1]
    print(ans)        




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
    

    dic2 = [(0,0)]
    while u:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
        dic2.sort()

    solve(dic2,dic,l)

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

#print(vw)
A = 12
N = min(1<<A,n+1)
"""
memo = [[(0,0)] for _ in range(N)]


memo[1].append((vw[1][1],vw[1][0]))

for i in range(2,N):
    v,w = vw[i]
    m2 = [(w+w1,v+v1) for w1,v1 in memo[i>>1]]
    
    idx = 0
    L = len(m2)
    for (w,v) in memo[i>>1][1:]:
        while m2[idx][0] < w and idx < L:
            w2,v2 = m2[idx]
            memo[i].append((w2,max(v2,memo[i][-1][1])))
            idx += 1
        memo[i].append((w,max(v,memo[i][-1][1])))
    for w,v in m2[idx:]:
        memo[i].append((w,max(v,memo[i][-1][1])))
        
#print(memo)

    #memo[i] = memo[i>>1] + [(w+w1,v+v1) for w1,v1 in memo[i>>1]]

#print(memo)
"""

"""
for i in range(1,N):
    memo[i].sort()
    L = len(memo[i])
    for j in range(1,L):
        I,J = memo[i][j]
        if J >= memo[i][j-1][1]:
            memo[i][j] = (I,J)
"""    
        
from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    #print(lst)
    for w,v in dic:
        idx = bisect_left(lst, (l+1-w,0))-1
        if idx >= 0 and v+lst[idx][1] > ans:
            ans = v+lst[idx][1]
    print(ans)        




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
    

    dic2 = [(0,0)]
    while u:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
        dic2.sort()

    solve(dic2,dic,l)