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 = sys.stdin.readline

N = int(input())
VW = [[0, 0]] + [[int(i) for i in input().split()] for _ in range(N)]
Q = int(input())
vL = [[int(i) for i in input().split()] for _ in range(Q)]
  
def solve(N, W, S):
  def make(S):
    T = {0: 0}
    for v, w in S:
      T0 = dict(T)
      for k, val in T.items():
        if k+w > W:
          continue
        if k+w in T0:
          T0[k+w] = max(T0[k+w], val + v)
        else:
          T0[k+w] = val + v
      T = T0
    v = 0
    R = []
    for k in sorted(T):
      v = max(v, T[k])
      R.append((k, v))
    return R

  def solve(T0, T1):
    T0.sort()
    T1.sort(reverse=1)
    it = iter(T1)
    k1, v1 = next(it)
    M = 0
    for k0, v0 in T0:
      while k0 + k1 > W:
        k1, v1 = next(it)
      M = max(M, v0 + v1)
    return M
  T0 = make(S[:N//2])
  T1 = make(S[N//2:])

  return solve(T0, T1)
  
for v, L in vL :
  s = []
  c = 0
  while v != 0 :
    s.append(VW[v])
    v //= 2
    c += 1
  print(solve(c, L, s))

Submission status: Time Limit Exceeded

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

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

    VW = [list(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(MAX_W):
            # print (i, j)
            if (j < W):
                dp[i][j] = dp[i // 2][j]
            else:
                dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)


    def calc(n, L):
        ans = 0
        lst = []
        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
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

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

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

# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        ll = l + list((ww+W[v], vv+V[v]) for ww,vv in l)
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
                
        d[v] = tmp
        q.appendleft(v)

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

Submission status: 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='i8')
    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)
    def r(n):
        #print(n)
        if visited[n-1]:
            return dps[n]
        visited[n-1]=1

        par=n//2
        r(par)
        dp=dps[par]
        ndp=np.copy(dp)
        v,w=costs[n-1]
        #if n==4:
            #print(par)
            #print(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        if w<=maxL:
            ndp[w:maxL+1]=np.maximum(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        dps[n]=ndp
        return ndp
        
    for v,L in qs:
        dp=r(v)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
M = 10 ** 5 + 1
K = 10
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
            vv = VV[i-a] + V[b]
            VV[i] = vv
            if ww <= maw:
                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
            vv = VV[i-a] + V[b]
            VV[i] = vv
            if ww > maw: continue
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

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)
    dic.sort()
    idx = len(lst)
    for w,v in dic:
        idx = bisect_left(lst, (l+1-w,0),hi=idx)-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:
        v,w = vw[u]
        dic += [(w+w1,v+v1) for w1,v1 in dic]
        u >>= 1
    
    solve(memo[u],dic,l)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
VW = []
for _ in range(N):
  VW.append(list(map(int,input().split())))
Q = int(input())

memo = {}
 
 
 
def select_or(weight,n, L):
  if n == 1:
    if weight + VW[0][1] <= L:
      return VW[0][0]
    else:
      return 0
  else:
    key = str(n) + "," + str(L-weight)
    if key in memo:
        return memo[key]
    else:
      if weight + VW[n-1][1] <= L:
        a = max(VW[n-1][0] + select_or(weight + VW[n-1][1],n//2,L), select_or(weight,n//2,L))
        memo[key] = a
        return a
      else:
        a = select_or(weight,n//2,L)
        memo[key] = a
        return a
    
  
 
for _ in range(Q):
  v,l = list(map(int,input().split())) 
  ans = select_or(0,v,l)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
V = []
W = []
for i in range(N):
    v,w = map(int,input().split())
    V.append(v)
    W.append(w)

dp = [[0]*(10**5+1) for _ in range(min(2**9,N+1))]

for n in range(1,min(2**9,N+1)):
    for l in range(10**5+1):
        c = 0
        if l>=W[n-1]:
            c = dp[n//2][l-W[n-1]]+V[n-1]
        dp[n][l] = max(dp[n//2][l],c)

for n in range(min(2**9,N+1)):
    for l in range(1,10**5+1):
        dp[n][l] = max(dp[n][l],dp[n][l-1])

memo = {}
def rec(n,l):
    if n < 2**9:
        return dp[n][l]
    elif (n,l) in memo:
        return memo[(n,l)]
    else:
        c = 0
        if l>=W[n-1]:
            c = rec(n//2,l-W[n-1])+V[n-1]
        res = max(rec(n//2,l),c)
        memo[(n,l)] = res
        return res

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

for i in range(Q):
    v,L = vL[i]
    print(rec(v,L))

Submission status: Time Limit Exceeded

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


def get_dp(V, W, node, memo):
    if memo[node-1]:
        return memo[node-1]
    if node == 1:
        memo[node-1] = [(0, 0), (W[0], V[0])]
        return memo[node-1]
    v = V[node-1]
    w = W[node-1]
    par = get_dp(V, W, node//2, memo)
    idx1 = 0
    idx2 = 0
    ret = []
    maxval = 0
    while idx1 < len(par) or idx2 < len(par):
        if idx1 < len(par) and par[idx1][0] <= par[idx2][0] + w:
            if par[idx1][0] == par[idx2][0] + w and par[idx1][1] < par[idx2][1] + v:
                maxval = max(maxval, par[idx2][1]+v)
                nxt = (par[idx2][0]+w, maxval)
                idx2 += 1
            else:
                maxval = max(maxval, par[idx1][1])
                nxt = (par[idx1][0], maxval)
                idx1 += 1
        else:
            maxval = max(maxval, par[idx2][1]+v)
            nxt = (par[idx2][0]+w, maxval)
            idx2 += 1
        ret.append(nxt)
    memo[node-1] = ret
    return ret


def bin_search(lst, value):
    lo = 0
    hi = len(lst)
    while lo < hi:
        mid = (lo + hi) // 2
        if lst[mid][0] > value:
            hi = mid
        else:
            lo = mid + 1
    return lo


def query(V, W, node, L, memo):
    par = get_dp(V, W, node, memo)
    v = V[node-1]
    w = W[node-1]
    idx = bin_search(par, L) - 1
    return par[idx][1]


def main():
    N = int(input())
    V = [0] * N
    W = [0] * N
    for i in range(N):
        V[i], W[i] = map(int, input().split())
    memo = [None] * N
    Q = int(input())
    for i in range(Q):
        v, L = map(int, input().split())
        ans = query(V, W, v, L, memo)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
M = 10 ** 5 + 1
K = 9
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
            vv = VV[i-a] + V[b]
            VV[i] = vv
            if ww <= maw:
                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
            vv = VV[i-a] + V[b]
            VV[i] = vv
            if ww > maw: continue
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

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 = 10
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]
            #if memo[i][-1][0] < w2: 
            memo[i].append((w2,max(v2,memo[i][-1][1])))
            idx += 1
        #if memo[i][-1][0] < w: 
        memo[i].append((w,max(v,memo[i][-1][1])))
    for w,v in m2[idx:]:
        #if memo[i][-1][0] < w: 
        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)
    dic.sort()
    idx = len(lst)-1
    #print(lst,l)
    for w,v in dic:
        while idx >= 0 and lst[idx][0] + w > l:
            idx -= 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:
        v,w = vw[u]
        dic += [(w+w1,v+v1) for w1,v1 in dic]
        u >>= 1
    
    solve(memo[u],dic,l)

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


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

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]
until = min(n, 2**10-1)
# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        ll = l + list((ww+W[v], vv+V[v]) for ww,vv in l)
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
                
        d[v] = tmp
        q.appendleft(v)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
from bisect import bisect_left
import math
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    V = [[] for _ in range(N+1)]
    W = [[] for _ in range(N+1)]
    for i in range(1,N+1):
        v, w = map(int, readline().split())
        if i == 1:
            V[i] = [v]
            W[i] = [w]
        else:
            V[i] = V[i//2] + [v]
            W[i] = W[i//2] + [w]

    Q = int(readline())
    for _ in range(Q):
        v, L = map(int, readline().split())
        dp = [0] * (L + 1)
        V1 = V[v]
        W1 = W[v]
        length = len(V1)
        for i in range(length):
            for j in range(L, -1, -1):
                if j - W1[i] >= 0:
                    dp[j] = max(dp[j], dp[j - W1[i]] + V1[i])
        print(dp[L])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
  N = int(input())
  item = [[0,0] for i in range(N)]
  
  for i in range(N):
    v,w = map(int,input().split())
    item[i][0] = v
    item[i][1] = w
    
  Q = int(input())
  
  def path(n):
    way = [n]
    if n == 1:
      return way
    else:
      while n > 1:
        n = n // 2
        way.append(n)
      return way[::-1]
  
  for q in range(Q):
    edge,lim = map(int,input().split())
    P = path(edge)
    #print(P)
    total = 0
    dp = np.zeros(lim + 2,dtype = int)
    for j in P:
      k = j - 1
      value = item[k][0]
      weight = item[k][1]
      if weight > lim:
        continue
      dp[weight:] = np.maximum(dp[weight:],dp[:-weight] + value)
    print(dp[lim])
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    V = [(next(it), next(it)) for i in range(N)]
    Q = next(it)

    bi = N.bit_length()
    B = [1<<i for i in range(bi)]

    x = 1
    for vi, li in zip(it, it):
        aa = []
        ans = 0
        while vi:
            if V[vi-1][1] <= li:
                aa.append(V[vi-1])
            vi >>= 1

        bi = len(aa).bit_length()
        ng = []
        for i in range(1, 1<<len(aa)):
            wi = vi = 0
            if any(i & j == j for j in ng):
                continue
            for j, jj in zip(range(bi+1), B):
                if i & jj:
                    wi += aa[j][1]
                    if wi > li:
                        ng.append(i)
                        break
                    vi += aa[j][0]
            else:
                ans = max(ans, vi)
        print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
vw = []
for i in range(n):
  vw.append(tuple(map(int,input().split())))
q = int(input())
for i in range(q):
  v,l = map(int,input().split())
  d = []
  while(v > 0):
    d.append(vw[v-1])
    v //= 2
  dp = [[0 for _ in range(10**5+1)] for _ in range(len(d)+1)]
  for j in range(len(d)):
    for k in range(10**5+1):
      dp[j+1][k] = dp[j][k]
      if k-d[j][1] >= 0:
        dp[j+1][k] = max(dp[j][k],dp[j][k-d[j][1]]+d[j][0])
  print(dp[len(d)][l])

Submission status: Time Limit Exceeded

Solution code:
import sys


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

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

    q = int(input())
    v_to_il = [[] for _ in range(n)]
    flag = [False] * n
    for i in range(q):
        v, l = map(int, input().split())
        v -= 1
        v_to_il[v].append((i, l))
        flag[v] = True
        while v > 0:
            v = (v - 1) // 2
            if flag[v]:
                break
            flag[v] = True

    MAX = 10**5
    # dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
    dp = [[0] * (MAX + 1) for _ in range(19)]
    ans = [0] * q

    def dfs(v, depth):
        val, w = items[v]
        for j in range(MAX + 1):
            if j < w:
                dp[depth + 1][j] = dp[depth][j]
            else:
                dp[depth + 1][j] = max(dp[depth][j], dp[depth][j - w] + val)

        if len(v_to_il[v]) > 0:
            for i, l in v_to_il[v]:
                ans[i] = dp[depth + 1][l]

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            dfs(v * 2 + 1, depth + 1)
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            dfs(v * 2 + 2, depth + 1)

    dfs(0, 0)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
V = []
W = []
LL = 10 ** 5 + 1
for _ in range(N):
    v, w = map(int, input().split())
    V.append(v)
    W.append(w)

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

dp = [[0] * LL]
# dp[0][W[0]] += V[0]

ans = [0] * Q

def dfs(i):
    dpi = []
    v, w = V[i-1], W[i-1]
    for item in dp[-1]:
        dpi.append(item)
    for j in range(LL):
        if j + w < LL:
            dpi[j+w] = max(dp[-1][j] + v, dpi[j+w])
    for qi, L in Memo[i-1]:
        ans[qi] = max(dpi[:L+1])
    dp.append(dpi)
    for ni in (i*2, i*2+1):
        if ni <= N:
            dfs(ni)
            dp.pop()

dfs(1)

for ansi in ans:
    print(ansi)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
V = [0] * N
W = [0] * N
for n in range(N):
  V[n], W[n] = [int(x) for x in input().split(' ')]
Q = int(input())
X = [0] * Q
L = [0] * Q
for q in range(Q):
  X[q], L[q] = [int(x) for x in input().split(' ')]

  
DP = [None] * N  # max value when weight total is equal or less than index
M = 10 ** 5 + 5
def dp(x):
  if DP[x] is not None:
    return DP[x]
  if x == 0:
    prev = [(0, 0)]
  else:
    prev = dp((x+1)//2-1)
  # print(x, prev)
  tmp = []
  W_todo = True
  for w, v in prev:
    tmp.append((w, v))
    tmp.append((w + W[x], v + V[x]))
  tmp = sorted(tmp, key=lambda p: (p[0], -p[1]))
  DP[x] = []
  current_v = -1
  for w, v in tmp:
    if v > current_v:
      DP[x].append((w, v))
      current_v = v
  return DP[x]

def solve(x, l):
  tmp = dp(x-1)
  current_v = -1
  for w, v in tmp:
    if w <= l:
      current_v = v
  return current_v

for x, l in zip(X, L):
  print(solve(x, l))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
q=int(input())
L=[list(map(int,input().split())) for i in range(q)]
dp=[[0]*(10**5+1) for i in range(n+2)]
for i in range(1,n+1):
  for j in range(10**5+1):
    if j>=l[i-1][1]:
      dp[i][j]=max(dp[i//2][j-l[i-1][1]]+l[i-1][0],dp[i][j],dp[i//2][j])
    else:
      dp[i][j]=dp[i//2][j]
for i in range(q):
  print(dp[L[i][0]][L[i][1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
import numpy as np


def f(li, w_max):
    d = defaultdict(int)
    for i in range(1 << len(li)):
        v_sm = 0
        w_sm = 0
        now = i
        cnt = 0
        while now:
            if now & 1:
                j = li[cnt]
                v, w = V[j-1], W[j-1]
                v_sm += v
                w_sm += w

            now >>= 1
            cnt += 1

        if w_sm <= w_max:
            d[w_sm] = max(d[w_sm], v_sm)

    return d


n = int(readline())
Z = np.array(read().split(), np.int64)
V = Z[0:2*n:2]
W = Z[1:2*n:2]
Q = Z[2*n]
U = Z[2*n+1::2]
L = Z[2*n+2::2]

for u, l in zip(U, L):
    li = []
    now = u
    while now:
        li.append(now)
        now //= 2

    ln = len(li)
    d1 = f(li[:ln//2], l)
    d2 = f(li[ln//2:], l)

    W2 = np.array(list(d2.keys()), np.int64)
    V2 = np.array(list(d2.values()), np.int64)
    idx = np.argsort(W2)
    W2 = W2[idx]
    V2 = V2[idx]
    V2 = np.maximum.accumulate(V2)
    #print(W2)
    #print(V2)

    ans = 0
    K1 = np.array(list(d1.keys()), np.int64)
    V1 = np.array(list(d1.values()), np.int64)
    IDX = np.searchsorted(W2, l - K1, "right") - 1
    VAL = V1 + V2[IDX]
    ans = VAL.max()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
lines = sys.stdin.readlines()

#N = int(input())
#VW = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#Q = int(input())
#vL = [list(map(int,input().split())) for i in range(Q)]
#vs,Ls = zip(*vL)

N = int(lines[0])
Q = int(lines[N+1])
vL = [list(map(int,s.split())) for s in lines[N+2:]]
vs,Ls = zip(*vL)
VW = {}

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = list(set(appear))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

for v in appear:
    VW[dic[v]] = list(map(int, lines[v].split()))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL+2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        s = dic[s]
        ns = dic[ns]
        V,W = VW[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[dic[orgv]][L])

for a in ans:
    print(a)