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 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 [W2, V2]


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
def f2(A, v, L, K):
    T = []
    while v >= 2 ** P:
        T.append(A[v - 1])
        v = v >> 1

    K2 = K.setdefault(v, make(A, v))
    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(K2[0], R)
        res = max(res, V + K2[1][min(t, len(K2)) - 1])

    return res



def main():
    N = int(input())
    A = read_lists(N)
    D = N.bit_length()

    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:
            ans[q] = str(f2(A, v, L, K))

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
VW=[]
for i in range(n):
    v,w=map(int,input().split())
    VW.append((v,w))


# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    # S[i] = (v, w): 価値v, 重さw
    *S, = zip(vs, ws)

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

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

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

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

    # 2つの全列挙を元に解を求める
    return max(solve(T0, T1))
VE=[[] for i in range(n)]
WE=[[] for i in range(n)]

q=int(input())
for _ in range(q):
    v,l=map(int,input().split())
    VS,WS=[],[]
    cur=v-1
    if VE[v-1]:
      VS=VE[v-1]
      WS=WE[v-1]
    else:
      while v>0:
        VS.append(VW[v-1][0])
        WS.append(VW[v-1][1])
        v//=2
        if VE[v-1]:
          VS+=VE[v-1]
          WS+=WE[v-1]
          v=0
    n=len(VS)
    VE[cur]=VS
    WE[cur]=WS
    print(solve(n, l, WS, VS))

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

MAX = int(1e5)


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
        if nxt[0] > MAX:
            break
        ret.append(nxt)
    if node < 2**9:
        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:
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])
        else:
            break
    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:
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 = 11
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)
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = len(knapls[anc])
      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:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
VW=[]
for i in range(n):
    v,w=map(int,input().split())
    VW.append((v,w))


# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    # S[i] = (v, w): 価値v, 重さw
    *S, = zip(vs, ws)

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

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

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

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

    # 2つの全列挙を元に解を求める
    return max(solve(T0, T1))
VE=[[] for i in range(n)]
WE=[[] for i in range(n)]

q=int(input())
for _ in range(q):
    v,l=map(int,input().split())
    VS,WS=[],[]
    if VE[v-1]:
      VS=VE[v-1]
      WS=WE[v-1]
    else:
      while v>0:
        VS.append(VW[v-1][0])
        WS.append(VW[v-1][1])
        v//=2
        if VE[v-1]:
          VS+=VE[v-1]
          WS+=WE[v-1]
          v=0
    n=len(VS)
    print(solve(n, l, WS, VS))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import product
    from operator import itemgetter
    n = int(input())
    vw = [list(map(int, readline().split())) for _ in range(n)]
    q = int(input())

    for _ in range(q):
        v, l = map(int, readline().split())
        nap = []

        while v > 0:
            nap.append(vw[v - 1])
            v //= 2

        num = len(nap)

        nap_first = nap[:(num + 1) // 2]
        nap_second = nap[(num + 1) // 2:]

        set_first = []
        len_nf = len(nap_first)

        for bit in product(range(2), repeat=len_nf):
            cur_v = 0
            cur_w = 0
            for i in range(len_nf):
                if bit[i] == 1:
                    cur_v += nap_first[i][0]
                    cur_w += nap_first[i][1]
            set_first.append((cur_v, cur_w))

        if not set_first:
            set_first.append((0, 0))

        set_second = []
        len_ns = len(nap_second)

        for bit in product(range(2), repeat=len_ns):
            cur_v = 0
            cur_w = 0
            for i in range(len_ns):
                if bit[i] == 1:
                    cur_v += nap_second[i][0]
                    cur_w += nap_second[i][1]
            set_second.append((cur_v, cur_w))

        if not set_second:
            set_second.append((0, 0))

        set_first.sort(key=itemgetter(1))
        set_second.sort(key=itemgetter(1))

        res = 0

        true_first = []

        mx = -1
        for vf, wf in set_first:
            if vf <= mx:
                pass
            else:
                true_first.append((vf, wf))
                mx = vf

        true_second = []
        mx = -1
        for vs, ws in set_second:
            if vs <= mx:
                pass
            else:
                true_second.append((vs, ws))
                mx = vs

        for vf, wf in true_first:
            for vs, ws in true_second:
                if wf + ws > l:
                    break
                else:
                    res = max(res, vs + vf)

        print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())

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

a = [[] for i in range(2**10)]

for i in range(1,min(n+1,2**10)):
    if i == 1:
        a[i].append((w[1],v[1]))
    else:
        p = i//2
        tank = set([(w[i],v[i])])
        for ww,vv in a[p]:
            tank.add((ww,vv))
            if ww + w[i] <= 10**5:
                tank.add((ww+w[i],vv+v[i]))
        tank = list(tank)
        tank.sort()
        ma = -1
        for j in range(len(tank)):
            ww,vv = tank[j]
            if vv > ma:
                if j == len(tank)-1 or tank[j+1][0] != ww:
                    ma = vv
                    a[i].append((ww,vv))



Q = int(input())
for _ in range(Q):
    now,L = map(int,input().split())
    if now < 2**10:
        if a[now][0][0] > L:
            print(0)
        else:
            ok = 0
            ng = len(a[now])

            while ng - ok > 1:
                mid = (ok+ng)//2
                if a[now][mid][0] > L:
                    ng = mid
                else:
                    ok = mid
            print(a[now][ok][1])
    else:
        pp = [(0,0)]
        while now >= 2**10:
            tank = []
            for ww,vv in pp:
                if ww+w[now] <= L:
                    tank.append((ww+w[now],vv+v[now]))
            for e in tank:
                pp.append(e)
            now = now//2

        pp.sort()
        res = 0
        ma = -1
        for ww,vv in pp:
            if ma < vv:
                ma = vv
                L -= ww
                if a[now][0][0] > L:
                    res = max(res,vv)
                else:
                    ok = 0
                    ng = len(a[now])

                    while ng - ok > 1:
                        mid = (ok+ng)//2
                        if a[now][mid][0] > L:
                            ng = mid
                        else:
                            ok = mid
                    res = max(res,a[now][ok][1] + vv)

                L += ww
        print(res)

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

    queue = [(0, 0)]
    while queue:
        v, depth = queue.pop()
        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]:
            queue.append((v * 2 + 1, depth + 1))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())

#iまでのアイテムで合計がL以下の最大値
dp = [[0 for j in range(10**5+1)] for _ in range(2 ** 7 + 1)]
vwl = [list(map(int,input().split())) for _ in range(n)]

for i in range(min(2**7, n)):
    v, w = vwl[i]
    for j in range(10**5+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[(i+1) // 2][j-w] + v, dp[(i+1) // 2][j])
        else:
            dp[i+1][j] = dp[(i+1) // 2][j]

from itertools import product
q = int(input())
for _ in range(q):
    v,l = map(int,input().split())
    items = []
    while v > 2**7:
        items.append(v)
        v //= 2
    ans = dp[v][l]
    for bits in product([0, 1], repeat=len(items)):
        weight = 0
        value = 0
        for idx, bit in enumerate(bits):
            weight += vwl[items[idx]-1][1] * bit
            value += vwl[items[idx]-1][0] * bit
        if weight > l:
            continue
        ans = max(dp[v][l-weight]+value, ans)
    print(ans)

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 [W2, V2]


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
def f2(A, v, L, K):
    T = []
    while v >= 2 ** P:
        T.append(A[v - 1])
        v = v >> 1

    K2 = K.setdefault(v, make(A, v))
    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(K2[0], R)
        res = max(res, V + K2[1][min(t, len(K2)) - 1])

    return res



def main():
    N = int(input())
    A = read_lists(N)
    D = N.bit_length()

    K = dict()
    if D > P:
        for i in range(2 ** (P - 1), 2 ** P):
            K[i] = make(A, i) 

    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:
            ans[q] = str(f2(A, v, L, K))

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MAX = int(1e5)


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
        if nxt[0] > MAX:
            break
        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()
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.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:
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(l+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:
def main():
    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))

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='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
        dp=np.copy(r(par))
        

        v,w=costs[n-1]
        #if n==4:
            #print(par)
            #print(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        if w<=maxL:
            dp[w:maxL+1]=np.maximum(dp[0:maxL+1-w]+v,dp[w:maxL+1])
        dps[n]=dp
        return dp
        
    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:
from math import floor, log2

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

lim = 100000

DP = {1:[0 for _ in range(VW[0][1])]}
DP[1].append(VW[0][0])
for i in range(Q):
  v, L = map(int, input().split())
  buf = []
  while v >= 1:
    if v in DP:
      break
    buf.append(v)
    v = v//2
  dp = DP[v]
  while len(buf)>0:
    v = buf.pop(-1)
    weight = VW[v-1][1]
    value = VW[v-1][0]
    #print(v, weight, value)
    dpbuf = list(dp) + [dp[-1]]*weight
    dpbuf = dpbuf[:lim+1]
    for j in range(weight,len(dpbuf)):
      if len(dp)>j:
        dpbuf[j] = max(dp[j], dp[j-weight]+value)
      else:
        dpbuf[j] = max(dp[-1], dp[j-weight]+value)
    DP[v] = dpbuf
    dp = dpbuf
    #print(dpbuf)
  if len(DP[v])<L+1:
    print(DP[v][-1])
  else:
    print(DP[v][L])
#print(DP[8])