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:
def main(): 
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  from bisect import bisect

  n = int(readline())
  g = []
  for i in range(n):
    v,W = map(int,readline().split())
    g.append((v,W))

  q = int(readline())
  for i in range(q):
    V,w = map(int,readline().split())
    c = []
    ans = 0
    while V > 0:
      c.append(g[V-1])
      V //= 2
    d = []
    e = []
    h = n//2
    H = n-h
    for i in range(2**h):
      cw = 0
      cv = 0
      for j,cj in enumerate(c[:h]):
        if (i>>j)&1 == 1:
          cw += cj[1]
          cv += cj[0]
      d.append((cv,cw))

    for i in range(2**H):
      cw = 0
      cv = 0
      for j,cj in enumerate(c[h:]):
        if (i>>j)&1 == 1:
          cw += cj[1]
          cv += cj[0]
      e.append((cv,cw))

    from operator import itemgetter
    e = sorted(e,key=itemgetter(1))

    Ev = [0]
    Ew = [0]
    ch = 0
    for i in range(1,len(e)):
      ev,ew = e[i]
      if ev > ch:
        Ev.append(ev)
        Ew.append(ew)
        ch = ev

    for i in d:
      Cv,Cw = i
      if Cw > w:
        continue
      ind = bisect(Ew,w-Cw)
      cc = Cv+Ev[ind-1]
      ans = max(cc,ans)

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
VW = [0] + [list(map(int, readline().split())) for _ in range(N)]

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

ul_s = sorted(ul, reverse=True)

cache = [None] * (N + 1)
S = 10 ** 5 + 10
TABLE = defaultdict(int)


def solve(q, l):
    q = q[::-1]

    mi = -1
    for i in range(len(q)):
        x = q[i]
        if type(cache[x]) is np.ndarray:
            mi = i
        else:
            break

    x = q[mi]
    dp = cache[x] if mi != -1 else np.zeros(S, dtype=np.int64)

    q = q[mi + 1 :] if mi != -1 else q
    ans = calc(q, l, dp)
    return ans


def calc(q, l, dp):

    for u in q:
        v, w = VW[u]
        tmp = np.zeros(S, dtype=np.int64)
        tmp[w:] = dp[:-w] + v

        dp = np.maximum(dp, tmp)
        # cache[u] = np.copy(dp)
        cache[u] = dp

    return max(dp[: l + 1])


ans = []
for u, l in ul_s:
    q = []
    v = u
    while v != 1:
        q.append(v)
        v //= 2
    q.append(1)

    t = solve(q, l)
    TABLE[(u, l)] = t

for u, l in ul:
    ans.append(TABLE[(u, l)])


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

Submission status: Time Limit Exceeded

Solution code:
import copy, sys

input = sys.stdin.readline
n = int(input())
vw = []
for i in range(n):
    V, w = map(int, input().split())
    vw.append([V, w])
status = [False] * (n + 1)
status[0] = {0:0}
q = int(input())
for i in range(q):
    v, l = map(int, input().split())
    root = [v]
    while root[-1] != 1:
        root.append(root[-1] // 2)
    root.reverse()
    for j in root:
        v0, w0 = vw[j-1][0], vw[j-1][1]
        if status[j] == False:
            temp = copy.copy(status[j//2])
            keys = list(temp.keys())
            keys.sort(reverse = True)
            for k in keys:
                if k + w0 in keys:
                    temp[k + w0] = max(temp[k + w0], temp[k] + v0)
                else:
                    if k + w0 <= 10 ** 5:
                        temp[k + w0] = temp[k] + v0
            status[j] = temp
        else:
            pass
    temp2 = status[v]
    values = [temp2[i] for i in temp2.keys() if i <= l]
    print(max(values))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
vw=[[0,0]]+LL(n)
Q=N()
q=[0]*(n+1)
dp=[dict() for i in range(n+1)]
def nap(v,l):
    if l in dp[v]:
        return dp[v][l]
    if v==0:
        return 0
    V,W=vw[v]
    if l>=W:
        ans=max(nap(v//2,l-W)+V,nap(v//2,l))
    else:
        ans=nap(v//2,l)
    dp[v][l]=ans
    return ans
for i in range(Q):
    v,l=NM()
    print(nap(v,l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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



# wv = np.array([list(map(int, input().split())) for i in range(0, N)])

for v, l in vl:
    WVi = [] #[weght, value]
    while v !=0:
        e = [VW[v-1][1], VW[v-1][0]]
        WVi.append(e)
        v = v//2

    nn = len(WVi) #アイテム数
    wv= np.array(WVi)
    # DPテーブル
    dp = np.zeros((nn+1, l+1), dtype=int)


    for n in range(nn - 1, -1, -1):
        for w in range(0, l + 1):
          if w < wv[n, 0]:
            dp[n, w] = dp[n + 1, w]
          else:
            dp[n, w] = max(dp[n+1, w], dp[n+1, w - wv[n, 0]] + wv[n, 1])

    print(dp[0, l])

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 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[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, (R, 10 ** 10))
        res = max(res, V + K2[min(t, len(K2)) - 1][1])

    return res


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

    K2 = [(0, 0)]
    mv = 0
    for w, v in K:
        if v <= mv:
            continue

        mv = v
        K2.append((w, mv))

    return K2


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:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


N = INT()
V, W = [], []
for _ in range(N):
    vi, wi = MAP()
    V.append(vi); W.append(wi)

Q = INT()
v, L = [], []
used_v = [False] * N
L_max = 0
for _ in range(Q):
    vi, li = MAP()
    vi -= 1
    v.append(vi); L.append(li)
    L_max = max(L_max, li)

    used_v[vi] = True
    while vi > 0:
        vi = (vi+1)//2-1
        if used_v[vi]:
            break



dp = [[0] * (L_max + 1) for _ in range(N)]
for j in range(L_max+1):
    if j < W[0]:
        continue
    dp[0][j] = V[0]

for i in range(1, N):
    if not(used_v):
        # print("skipped")
        continue

    for j in range(1, L_max + 1):
        if j < W[i]:
            dp[i][j] = dp[(i+1)//2-1][j]
        else:
            dp[i][j] = max(dp[i][j-1], dp[(i+1)//2-1][j-W[i]]+V[i], dp[(i+1)//2-1][j])


for i in range(Q):
    print(dp[v[i]][L[i]])

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline


def main():

    N = int(readline())
    th = []
    for _ in range(N):
        v, w = map(int, readline().split())
        th.append((v, w))

    Q = int(readline())
    ans = []
    for i in range(Q):
        v, l = map(int, readline().split())

        n = 0
        w = l
        t_th = []

        while True:
            t_th.append(th[v - 1])
            n += 1
            v = v // 2
            if v == 0:
                break

        ans.append(knap(n, w, t_th))

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


def knap(N, W, th):

    if N <= 30:
        tha = th[:(N // 2)]
        thb = th[(N // 2):]

        la, lb = len(tha), len(thb)
        ua, ub = [], []
        for i in range(1 << la):  # 1<<la = 2**la ex) 1<<1 = 10 = 2 ** 1
            v, w = 0, 0
            for j in range(la):
                if (i >> j) & 1 == 0:
                    v += tha[j][0]
                    w += tha[j][1]
            ua.append((v, w))
        for i in range(1 << lb):
            v, w = 0, 0
            for j in range(lb):
                if (i >> j) & 1 == 0:
                    v += thb[j][0]
                    w += thb[j][1]
            ub.append((v, w))
        # ubをwについて昇順に並べる
        ub.sort(key=lambda x: x[1])
        val = 0
        use_val, use_we = [], []
        # uvを昇順にする
        for v, x in ub:
            val = max(val, v)
            use_val.append(val)
            use_we.append(x)
        ans = 0
        # uaのひとつの要素について考える
        for v, w in ua:
            cost = v
            if w > W:
                continue
            rest = W - w
            # 残りのwでギリギリのところを探す
            ind = bisect.bisect_right(use_we, rest) - 1
            cost += use_val[ind]
            # 前の要素について考えたときより大きいかどうか判定
            ans = max(ans, cost)
        return ans


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, data, value, weight): #コンストラクタ
        self.data = data #ノードがもつ数値
        self.value = value
        self.weight = weight
        self.left = None #左エッジ
        self.right = None #右エッジ

class BST:
    def __init__(self, number_list): #コンストラクタ
        self.root = None #ルートノード初期化
        for node in number_list: #数値を持つ配列から二分木を生成
            self.insert(*node) #挿入メソッドを使ってノードを挿入する
    #挿入
    def insert(self, data, value, weight):
        n = self.root
        if n == None:
            self.root = Node(data, value, weight)
            return
        else:
            pn = n
            cn = n
            for i, s in enumerate(bin(data)[3:]):
                if s == '0':
                    pn = cn
                    cn = cn.left
                else:
                    pn = cn
                    cn = cn.right
            if s == '0':
                pn.left = Node(data, value, weight)
            else:
                pn.right = Node(data, value, weight)

n = int(input())
vw = []
for j in range(n):
    vw.append([j+1] + [int(i) for i in input().split()])

q = int(input())
vl = []
for _ in range(q):
    vl.append([int(i) for i in input().split()])

tree = BST(vw)
  
def knapsack(i, w):
    if i>=len(items):
        return 0
    elif  w - items[i][1] < 0.0:
        return knapsack(i+1, w)
    else:
        return max(knapsack(i+1, w), knapsack(i+1, w - items[i][1]) + items[i][0])

for li in vl:
  targets = bin(li[0])[3:]
  cn = tree.root
  items = [[cn.value, cn.weight]]
  for i, s in enumerate(targets):
    if s == '0':
      cn = cn.left
    else:
      cn = cn.right
    items.append([cn.value, cn.weight])
  print(knapsack(0, li[1]))

Submission status: Time Limit Exceeded

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

N = int(input())
V = []
W = []
for n in range(N):
  V_, W_ = map(int, input().split())
  V.append(V_)
  W.append(W_)
Q = int(input())

def query(v, L):
  vlist = []
  while v > 0:
    vlist.append(v)
    v = v // 2
  lenlist = len(vlist)
  dp = [[0] * (L+1) for l in range(lenlist + 1)]
  for k in range(lenlist):
    for l in range(L+1):
      if l < W[vlist[k]-1]:
        dp[k+1][l] = dp[k][l]
      else:
        dp[k+1][l] = max(dp[k][l], dp[k][l-W[vlist[k]-1]] + V[vlist[k]-1])
  print(dp[lenlist][L])


for q in range(Q):
  v, L = map(int, input().split())
  query(v, L)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from itertools import accumulate
from collections import defaultdict
import bisect
input = sys.stdin.buffer.readline

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

dp_dict = [defaultdict(lambda: 0)]
dp_dict[0][0] = 0
dp_dict[0][vws[0][1]] = vws[0][0]

for i in range(1, min(2**13, N)):
    v, w = vws[i]
    dp_dict.append(dp_dict[(i-1)//2].copy())
    for w_sum, v_sum in dp_dict[(i-1)//2].items():
        dp_dict[i][w_sum + w] = max(v_sum + v, dp_dict[i][w_sum + w])

values_list = []
weights_list = []
for d in dp_dict:
    ls = sorted(d.items(), key = itemgetter(0))
    weights, values = zip(*ls)
    values = list(accumulate(values, max))
    values_list.append(values)
    weights_list.append(weights)
        
Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    if V-1 < len(dp_dict):
        index = bisect.bisect_right(weights_list[V-1], L) - 1
        print(values_list[V-1][index])
    else:
        V -= 1
        d = defaultdict(lambda: 0)
        d[0] = 0
        while V >= len(dp_dict):
            v, w = vws[V]
            iterator = list(d.items())
            for w_sum, v_sum in iterator:
                d[w_sum + w] = max(v_sum + v, d[w_sum + w])
            V = (V-1) // 2

        v_max = 0
        for w1, v1 in d.items():
            index = bisect.bisect_right(weights_list[V], L-w1) - 1
            if index == -1:
                continue
            v_max = max(v_max, v1 + values_list[V][index])
        print(v_max)

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**9)]

for i in range(1,min(n+1,2**9)):
    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**9:
        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**9:
            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
        
        res = 0

        for ww,vv in pp:
            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:
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
    for k1, v1 in d1.items():
        i = np.searchsorted(W2, l - k1, "right")
        ans = max(ans, v1 + V2[i-1])

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from bisect import bisect_left,bisect_right
from itertools import accumulate

def solve1(N,W,item):
    #半分全列挙
    M = N//2
    former = [(0,0)]
    latter = [(0,0)]
    for v,w in item[:M]:
        former += [(x + v,y + w) for x,y in former]
    for v,w in item[M:]:
        latter += [(x + v,y + w) for x,y in latter]
    
    former.sort(key = lambda x:x[1])
    value = list(accumulate([v for v,w in former],max)) 
    weight = [w for v,w in former]
 
    ans = 0
    for v,w in latter:
        idx = bisect_right(weight,W - w) - 1
        if idx < 0:
            continue
        ans = max(ans,v + value[idx])
    print(ans)

def main():
    N = int(input())
    item = [tuple(map(int,input().split())) for _ in range(N)]
    Q = int(input())
    for _ in range(Q):
        V,L = map(int,input().split())
        items = []
        while V > 0:
            items.append(item[V - 1])
            V >>= 1
        M = len(items)
        solve1(M,L,items)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  vw = [[0,0]]+[tuple(map(int,input().split())) for i in range(n)]
  q = int(input())
  query = [tuple(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])
  def calc(v,L):
    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)
    return ans
  for v,L in query:
    if v >= 2**border:
      print(calc(v,L))
    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)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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')

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
VW = [0] + [list(map(int, readline().split())) for _ in range(N)]

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

# ul.sort(reverse=True)

cache = [None] * (N + 1)
S = 10 ** 5 + 10


def solve(q, l):
    q = q[::-1]

    mi = -1
    for i in range(len(q)):
        x = q[i]
        if type(cache[x]) is np.ndarray:
            mi = i
        else:
            break

    x = q[mi]
    dp = cache[x] if mi != -1 else np.zeros(S, dtype=np.int64)

    q = q[mi + 1 :] if mi != -1 else q
    ans = calc(q, l, dp)
    return ans


def calc(q, l, dp):

    for u in q:
        v, w = VW[u]
        tmp = np.zeros(S, dtype=np.int64)
        tmp[w:] = dp[:-w] + v

        dp = np.maximum(dp, tmp)
        # cache[u] = np.copy(dp)
        cache[u] = dp

    return max(dp[: l + 1])


ans = []
for u, l in ul:
    q = []
    v = u
    while v != 1:
        q.append(v)
        v //= 2
    q.append(1)

    t = solve(q, l)
    ans.append(t)

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

Submission status: Time Limit Exceeded

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

n = int(readline())
g = []
for i in range(n):
  v,W = map(int,readline().split())
  g.append((v,W))
  
q = int(readline())
for i in range(q):
  V,w = map(int,readline().split())
  c = []
  ans = 0
  while V > 0:
    c.append(g[V-1])
    V //= 2
  d = []
  e = []
  h = n//2
  H = n-h
  for i in range(2**h):
    cw = 0
    cv = 0
    for j,cj in enumerate(c[:h]):
      if (i>>j)&1 == 1:
        cw += cj[1]
        cv += cj[0]
    d.append((cv,cw))
    
  for i in range(2**H):
    cw = 0
    cv = 0
    for j,cj in enumerate(c[h:]):
      if (i>>j)&1 == 1:
        cw += cj[1]
        cv += cj[0]
    e.append((cv,cw))
    
  from operator import itemgetter
  e = sorted(e,key=itemgetter(1))
  
  Ev = [0]
  Ew = [0]
  ch = 0
  for i in range(1,len(e)):
    ev,ew = e[i]
    if ev > ch:
      Ev.append(ev)
      Ew.append(ew)
      ch = ev
  
  for i in d:
    Cv,Cw = i
    if Cw > w:
      continue
    ind = bisect(Ew,w-Cw)
    cc = Cv+Ev[ind-1]
    ans = max(cc,ans)
    
  print(ans)

Submission status: Time Limit Exceeded

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


# inpt N:number W:maxweight
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i + 1, w] = max(dp[i, w - weight[i]] + value[i], dp[i, w])
            else:
                dp[i + 1, w] = dp[i, w]
    
    return dp[N , W ]

def main():
    """"ここに今までのコード"""
    N = int(input())
    VW = []
    for _ in range(N):
        V, W = map(int, input().split())
        VW.append([V, W])

    VW = np.array(VW).reshape(N,2)
    V = VW[:,0]
    W = VW[:,1]

    Q = int(input())
    vL = []

    for _ in range(Q):
        v, L = map(int, input().split())
        vL.append([v, L])

    for vls in vL:
        v, L = vls
        vv = v
        
        value = [V[v - 1]]
        weight = [W[v - 1]]
        
        while vv > 0:
            vv = vv//2
            value.append(V[vv - 1])
            weight.append(W[vv - 1])
        
        # answer
        print(int(solveDP(len(value),L,value,weight)))

if __name__ == '__main__':
    main()

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())
        length = math.floor(math.log2(v)) + 1

        n1 = length//2
        n2 = length - n1
        V1 = V[v][:n1]
        W1 = W[v][:n1]
        V2 = V[v][n1:]
        W2 = W[v][n1:]
        pair1 = []

        ans = 0


        for i in range(2**n1):
            sw = 0
            sv = 0
            for j in range(n1):
                if (i>>j) & 1:
                    sw += W1[j]
                    sv += V1[j]
            pair1.append([sw,sv])

        pair1.sort()
        for i in range(2**n1-1):
            if pair1[i+1][1]<=pair1[i][1]:
                pair1[i+1] = pair1[i]

        for i in range(2**n2):
            sw = 0
            sv = 0


            for j in range(n2):
                if (i>>j) & 1:
                    sw += W2[j]
                    sv += V2[j]
            if sw<=L:
                left = 0
                right = 2**n1
                while right-left>1:
                    mid = (left+right)//2
                    if pair1[mid][0] + sw > L:
                        right = mid
                    else:
                        left = mid
                ans = max(pair1[left][1]+sv, ans)

        print(ans)
if __name__ == '__main__':
    main()