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 itertools

n = int(input())
p, w = [-1], [-1]
for i in range(n):
    vi, wi = map(int, input().split())
    p.append(vi)
    w.append(wi)
q = int(input())
query = [[-1, -1]]
for i in range(q):
    vi, li = map(int, input().split())
    query.append([vi, li])

c = 10**5
nn = 2**9 - 1
dp = [[-1 for j in range(c+1)] for i in range(nn+1)]
for i in range(c+1):
    if i >= w[1]:
        dp[1][i] = p[1]
    else:
        dp[1][i] = 0

for i in range(2, min(n+1, nn+1)):
    parent = i//2
    for j in range(c+1):
        if j >= w[i]:
            dp[i][j] = max(dp[parent][j-w[i]]+p[i], dp[parent][j])
        else:
            dp[i][j] = dp[parent][j]

for i in range(1, q+1):
    vi, li = query[i]
    if vi <= nn:
        print(dp[vi][li])
    else:
        lst = [vi]
        while vi//2 > nn:
            vi = vi // 2
            lst.append(vi)
        node = vi // 2
        length = len(lst)
        ans = 0
        for tup in itertools.product([0,1], repeat=length):
            price, weight = 0, 0
            for j in range(length):
                if tup[j] == 1:
                    price += p[lst[j]]
                    weight += w[lst[j]]
            if weight <= li:
                ans = max(ans, dp[node][li-weight]+price)
            else:
                ans = max(ans, dp[node][li])
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division

import sys
class Knapsack:
    def __init__(self, VW):
        self.VW = VW
        self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
        self.n = len(VW)
 
    def solve(self, capacity, ok=0):
        self.ok = ok
        self.capacity = capacity
        return self._dfs(0, 0, 0)
 
    def _dfs(self, i, v_now, w_now):
        if i==self.n:
            self.ok = max(self.ok, v_now)
            return v_now
        ng, f = self._solve_relaxation(i, self.capacity-w_now)
        ng += v_now
        if f:
            self.ok = max(self.ok, ng)
            return ng
        if ng < self.ok:
            return -float("inf")
        res = -float("inf")
        v, w = self.VW[i]
        if w_now + w <= self.capacity:
            res = max(res, self._dfs(i+1, v_now + v, w_now + w))
        res = max(res, self._dfs(i+1, v_now, w_now))
        return res
 
    def _solve_relaxation(self, i, capacity):
        res = 0
        f = True
        for v, w in self.VW[i:]:
            if capacity == 0:
                break
            if w <= capacity:
                capacity -= w
                res += v
            else:
                f = False
                res += v * (capacity / w)
                break
        return res, f
def main():
    input = sys.stdin.readline
    N = int(input())
    VW = [0] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        vw = []
        while V > 0:
            vw.append(VW[V])
            V //= 2
        knapsack = Knapsack(vw)
        ans = knapsack.solve(L)
        Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
import bisect

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	NN = 2 ** N.bit_length() - 1
	WWlist = [[] for i in range(NN)]
	X = [[0, 0] for i in range(NN)]
	for i in range(N):
		V, W = getlist()
		X[i] = [W, V]

	#前半までbit全探索
	WWlist[0].append([0, 0])
	WWlist[0].append(X[0])
	dep = min(2 ** (N.bit_length() - 1) - 1, 4095)
	# dep = 7
	for i in range(dep):
		u1 = 2 * i + 1
		u2 = 2 * i + 2
		for w, v in WWlist[i]:
			WWlist[u1].append([w, v])
			WWlist[u1].append([w + X[u1][0] , v + X[u1][1]])
			WWlist[u2].append([w, v])
			WWlist[u2].append([w + X[u2][0] , v + X[u2][1]])
		WWlist[u1].sort()
		WWlist[u2].sort()

	#価値を単調増加させる
	for i in range(dep * 2 + 1):
		for j in range(len(WWlist[i]) - 1):
			WWlist[i][j + 1][1] = max(WWlist[i][j + 1][1], WWlist[i][j][1])

	# print(WWlist)

	Q = int(input())
	for i in range(Q):
		v, L = getlist()
		v -= 1
		if v <= dep * 2 + 1:
			ind = bisect.bisect_left(WWlist[v], [L + 1, -INF]) - 1
			ans = WWlist[v][ind][1]
			print(ans)
		else:
			node = []
			while True:
				node.append(v)
				v = int((v - 1) // 2)
				if v <= dep * 2 + 1:
					x = v
					break

			M = len(node)
			WWW = []
			for p in range(1 << M):
				bitlist = []
				w = 0; v = 0
				for q in range(M):
					if ((p >> q) & 1) == 1:
						w += X[node[q]][0]
						v += X[node[q]][1]
			WWW.append([w, v])
			ans = 0
			for wd, vd in WWW:
				ind = bisect.bisect_left(WWlist[x], [L - wd + 1, -INF]) - 1
				ans = max(ans, vd + WWlist[x][ind][1])
			print(ans)



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    B = [[int(v) for v in input().split()] for _ in range(N)]
    WV = [None for _ in range(N)]
    Lim = pow(2, 10)
    WV[0] = [(0, 0), (B[0][1], B[0][0])]
    for i in range(1, min(N, Lim)):
        s = set()
        for w, v in WV[(i - 1)//2]:
            s |= {(w, v)}
            if w + B[i][1] <= 10 ** 5: s |= {(w + B[i][1], v + B[i][0])}
        WV[i] = sorted(s)
    
    for i in range(min(N, Lim)):
        for j in range(1, len(WV[i])):
            if WV[i][j-1][1] > WV[i][j][1]: WV[i][j] = (WV[i][j][0], WV[i][j-1][1])
    #print(WV)

    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        add = dict()
        add[0] = 0
        while v >= Lim:
            s = set()
            for w in add:
                val = add[w]
                if w + B[v-1][1] <= L:
                    s |= {(w+B[v-1][1], val + B[v-1][0])}
            for w, val in s:
                if w in add: add[w] = max(add[w], val)
                else: add[w] = val
            v //= 2
        ans = 0
        le = len(WV[v-1])
        for w in add:
            val = add[w]
            low, high = 0, le
            #print(WV[v-1], low, high, le, v-1)
            while high - low > 1:
                mid = (high + low) // 2
                if WV[v-1][mid][0] + w > L: high = mid
                else: low = mid
            ans = max(ans, val + WV[v-1][low][1])
        Ans[q] = ans

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    n = int(input())
    wv = []
    for _ in range(n):
        v, w = map(int, input().split())
        wv.append([w, v])

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma]
    for i in range(wv[0][0], ma):
        tab[0][i] = wv[0][1]

    for i in range(1, n2):
        j = (i - 1) // 2
        a = tab[j][:]
        l = 0
        for k in range(wv[i][0], ma):
            l = max((l, tab[j][k - wv[i][0]] + wv[i][1], a[k]))
            a[k] = l
        tab.append(a)

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [[0, 0]]
            while u >= n2:
                for i in a[:]:
                    if i[0] + wv[u][0] <= l:
                        a.append([i[0] + wv[u][0], i[1] + wv[u][1]])
                u = (u - 1) // 2
            ans = 0
            for i, j in a:
                ans = max(ans, tab[u][l - i] + j)
            print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n2 = max(1, min(n, int(n ** 0.5)))

ma = 10 ** 5 + 1
tab = [[0] * ma]
for i in range(wv[0][0], ma):
    tab[0][i] = wv[0][1]

for i in range(1, n2):
    j = (i - 1) // 2
    a = tab[j][:]
    l = 0
    for k in range(wv[i][0], ma):
        l = max((l, tab[j][k - wv[i][0]] + wv[i][1], a[k]))
        a[k] = l
    tab.append(a)

q = int(input())
for _ in range(q):
    u, l = map(int, input().split())
    u -= 1
    if u < n2:
        print(tab[u][l])
    else:
        a = [[0, 0]]
        while u >= n2:
            for i in a[:]:
                if i[0] + wv[u][0] <= l:
                    a.append([i[0] + wv[u][0], i[1] + wv[u][1]])
            u = (u - 1) // 2
        ans = 0
        for i, j in a:
            ans = max(ans, tab[u][l - i] + j)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 9
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

from itertools import accumulate

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = list(accumulate(m,max))


q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0
    for w,v in dic:
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, V: "List[int]", W: "List[int]", Q: int, VV: "List[int]", LL: "List[int]"):
    d = int(math.log(N, 2)) + 1
    #print(d)
    hd = d // 2 + 1
    max_m = 2 ** (d // 2) - 1
    dp = [{} for _ in range(max_m + 1)]
    dp[0] = {0: 0}
    for i in range(max_m):
        v, w = V[i], W[i]
        idx = i + 1
        par = idx // 2
        for ww, vv in dp[par].items():
            dp[idx][ww] = dp[par][ww]
        for ww, vv in dp[par].items():
            if ww + w in dp[idx]:
                dp[idx][ww + w] = max(dp[idx][ww + w], dp[par][ww] + v)
            else:
                dp[idx][ww + w] = dp[par][ww] + v
    items = []
    for i in range(max_m + 1):
        tmp = list(dp[i].items())
        tmp.sort()
        max_v = 0
        hoge = []
        for ww, vv in tmp:
            max_v = max(max_v, vv)
            hoge.append((ww, max_v))
        items.append(hoge)

    #print(dp)
    #print(items)

    for q in range(Q):
        ret = 0
        idx, l = VV[q], LL[q]
        pre = {0: 0}
        while idx > max_m:
            w, v = W[idx - 1], V[idx - 1]
            cur = {ww: vv for ww, vv in pre.items()}
            for ww, vv in pre.items():
                if ww + w in cur:
                    cur[ww + w] = max(cur[ww + w], cur[ww] + v)
                else:
                    cur[ww + w] = cur[ww] + v
            pre = cur
            idx //= 2
        #print(pre, items[idx], l)
        for ww, vv in pre.items():
            if l < ww:
                continue
            max_l = l - ww
            x = bisect.bisect_right(items[idx], (max_l, float('inf')))
            if x < 1:
                vvv = 0
            else:
                vvv = items[idx][x - 1][1]
            ret = max(ret, vv + vvv)
            #print(ww, vv, max_l, x, vvv, ret)
        print(ret)
        #print(' ************* ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    V = [int()] * (N)  # type: "List[int]"
    W = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        V[i] = int(next(tokens))
        W[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    v = [int()] * (Q)  # type: "List[int]"
    L = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        v[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, V, W, Q, v, L)

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack_meetinthemiddle(n, cap, item):
    if n % 2 != 0: item.append((0, 0))
    m = (n + 1) // 2
    M = 2**m
    item1 = item[:m]
    item2 = item[m:]
    S1 = [None] * (M)
    S2 = [None] * (M)
    for i in range(M):
        sumv1, sumw1, sumv2, sumw2 = 0, 0, 0, 0
        for j in range(m):
            if (i >> j) & 1:
                v1, w1 = item1[j]
                v2, w2 = item2[j]
                sumv1 += v1
                sumw1 += w1
                sumv2 += v2
                sumw2 += w2
        S1[i] = (sumw1, sumv1)
        S2[i] = (sumw2, sumv2)
    S1.sort()
    S2.sort()
    res, j, tmp = 0, 0, 0
    for sw1, sv1 in S1[::-1]:
        if sw1 > cap: continue
        while j < M and sw1 + S2[j][0] <= cap:
            tmp = max(tmp, S2[j][1])
            j += 1
        res = max(res, sv1 + tmp)
    return res

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

if N < 2**10:
    for _ in range(Q):
        u, L = map(int, input().split())
        item = []
        cnt = 0
        while u:
            item.append(I[u - 1])
            cnt += 1
            u //= 2
        print(knapsack_meetinthemiddle(cnt, L, item))

else:
    T = [[None] * (2**10) for _ in range(2**9)]
    for i in range(2**9, 2**10):
        for j in range(2**10):
            sumv, sumw = 0, 0
            for k in range(10):
                if (j >> k) & 1:
                    v, w = I[((i + 1) >> k) - 1]
                    sumv += v
                    sumw += w
            T[i - 2**9][j] = (sumw, sumv)
        T[i - 2**9].sort()

    for _ in range(Q):

        u, L = map(int, input().split())
        if u < 2**10:
            item = []
            cnt = 0
            while u:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            print(knapsack_meetinthemiddle(cnt, L, item))
        else:
            item = []
            cnt = 0
            while u >= 2**10:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            S = [None] * (2**cnt)
            for j in range(2**cnt):
                sumv, sumj = 0, 0
                for k in range(cnt):
                    if (j >> k) & 1:
                        v, w = item[k]
                        sumv += v
                        sumw += w
                S[j] = (sumw, sumv)
            S.sort()
            #T[u - 2**8]
            res, j, tmp = 0, 0, 0
            for sw, sv in S[::-1]:
                if sw > L: continue
                while j < 2**10 and sw + T[u - 2**9][j][0] <= L:
                    tmp = max(tmp, T[u - 2**9][j][1])
                    j += 1
                res = max(res, sv + tmp)
            print(res)

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])
  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)
      lknap = len(knapls[anc])
      for i in range(l):
        vn,wn = ls[i]
        rest = L-wn
        if i == 0:
          left = 0
          right = lknap
        elif wn >= wp:
          if vn <= vp:
            continue
          left = 0
        else:
          right = lknap
        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)
        vp,wp = vn,wn
      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)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    M = 2**10
    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(M,N+1))]

    for n in range(1,min(M,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(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    def cal(n,l):
        if n < M:
            return dp[n][l]
        else:
            v = []
            while n >= M:
                v.append(n)
                n //= 2
            m = len(v)
            res = dp[v[-1]//2][l]
            for n in range(2**m):
                v_tot = 0
                w_tot = 0
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[v[k]-1]
                        w_tot += W[v[k]-1]
                if w_tot <= l:
                    res = max(res,v_tot+dp[v[-1]//2][l-w_tot])
            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(cal(v,L))

if __name__ == '__main__':
    main()

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)
    lknap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      if i == 0:
        left = 0
        right = lknap
      elif wn >= wp:
        if vn <= vp:
          continue
        left = 0
      else:
        right = lknap
      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)
      vp,wp = vn,wn
    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


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, items_sub = queue.pop()
        val, w = items[v]

        if depth < 10:
            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)
        else:
            items_sub.append(v)

        if len(v_to_il[v]) > 0:
            if depth < 10:
                for i, l in v_to_il[v]:
                    ans[i] = dp[depth + 1][l]
            else:
                cand = 0
                m = len(items_sub)
                for bit in range(1 << m):
                    s_val = s_w = 0
                    for i, v in enumerate(items_sub):
                        if (bit >> i) & 1:
                            s_val += items[v][0]
                            s_w += items[v][1]
                    for i, l in v_to_il[v]:
                        if s_w <= l:
                            ans[i] = max(ans[i], dp[10][l - s_w] + s_val)

        if v * 2 + 1 < n and flag[v * 2 + 1]:
            queue.append((v * 2 + 1, depth + 1, items_sub))
        if v * 2 + 2 < n and flag[v * 2 + 2]:
            queue.append((v * 2 + 2, depth + 1, items_sub))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    B = [[int(v) for v in input().split()] for _ in range(N)]
    WV = [None for _ in range(N)]
    Lim = pow(2, 10)
    WV[0] = [(0, 0), (B[0][1], B[0][0])]
    for i in range(1, min(N, Lim)):
        s = set()
        for w, v in WV[(i - 1)//2]:
            s |= {(w, v)}
            if w + B[i][1] <= 10 ** 5: s |= {(w + B[i][1], v + B[i][0])}
        WV[i] = sorted(s)
    
    for i in range(min(N, Lim)):
        for j in range(1, len(WV[i])):
            if WV[i][j-1][1] > WV[i][j][1]: WV[i][j] = (WV[i][j][0], WV[i][j-1][1])
    #print(WV)

    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        add = set()
        add |= {(0, 0)}
        while v >= Lim:
            s = set()
            for w, val in add:
                if w + B[v-1][1] <= L:
                    s |= {(w+B[v-1][1], val + B[v-1][0])}
            add |= s
            v //= 2
        ans = 0
        le = len(WV[v-1])
        for w, val in add:
            low, high = 0, le
            #print(WV[v-1], low, high, le, v-1)
            while high - low > 1:
                mid = (high + low) // 2
                if WV[v-1][mid][0] + w > L: high = mid
                else: low = mid
            ans = max(ans, val + WV[v-1][low][1])
        Ans[q] = ans

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

    return 0

if __name__ == "__main__":
    solve()

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 operator import itemgetter
  from bisect import bisect_left

  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):
    p,w_max = map(int,readline().split())
    V = []
    W = []
    N = 0
    while p > 0:
      a,b = g[p-1]
      V.append(a); W.append(b)
      N += 1
      p //= 2
    left = [(0,0)] # weight, value
    right = [(0,0)]
    for i in range(N//2):
      left += [(x+W[i],y+V[i]) for x,y in left]
    for i in range(N//2,N):
      right += [(x+W[i],y+V[i]) for x,y in right]
    left.sort() # 重さ順
    right.sort()
    def remove_worthless(li):
      temp = []
      current_value = -1
      for w,v in li:
        if w > w_max:
          break
        # valueを更新したものに制限
        if v > current_value:
          current_value = v
          temp.append((w,v))
      return temp
    left = remove_worthless(left)
    right = remove_worthless(right)
    INF = 10**10
    right.append((INF,0))
    j = 0
    x = 0
    for wL,vL in left[::-1]:
      wR_max = w_max-wL
      while right[j+1][0] <= wR_max:
        j += 1
      vLR = vL + right[j][1]
      if x < vLR:
        x = vLR
    print(x)
if __name__ == '__main__':
    main()

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)
    lknap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      if i == 0:
        left = 0
        right = lknap
      elif wn >= ls[i-1][1]:
        left = 0
      else:
        right = lknap
      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:
N = int(input())

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

Q = int(input())

vS = []

for i in range(Q):
    v, l = (int(i) for i in input().split())
    vS.append((v,l))


for vs, l in vS:
    tmp = vs
    weight = []
    value = []
    while tmp != 0:
        weight.append(W[tmp-1])
        value.append(V[tmp-1])
        tmp = tmp // 2
    
 #   print("---")
 #   for i in range(len(weight)):
 #       print(value[i], weight[i])
 #   print("---")

    N = len(weight)

    dp = [[0] * (l+1) for i in range(N + 1)]

    for i in range(N):
        for w in range(l+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] 

#    for i in range(N+1):
#        for w in range(l+1):
#            print(dp[i][w], end=",")
#        print()
    print(dp[N][l])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
vws = []
for _ in range(n):
    v, w = map(int, input().split())
    vws.append((v, w))
q = int(input())
querys = []
for _ in range(q):
    v, l = map(int, input().split())
    querys.append((v, l))
def solve(vw, dp=None, l=10**5):
    if dp is None:
        dp = {0: 0}
    for va, we in vw:
        newdp = dp.copy()
        for w in dp:
            if w+we>l:
                continue
            if w+we in newdp.keys():
                if newdp[w+we]<dp[w]+va:
                    newdp[w+we] = dp[w]+va
            else:
                newdp[w+we] = dp[w]+va
        dp = newdp
    return dp
dps = []
PRE = min(512, n)
for ver in range(1, PRE+1):
    vw = []
    while ver>0:
        vw.append(vws[ver-1])
        ver//=2
    dps.append(solve(vw))
    
for ver, l in querys:
    if ver<=PRE:
        dp = dps[ver-1]
    else:
        vw = []
        while ver>PRE:
            vw.append(vws[ver-1])
            ver//=2
        dp = solve(vw, dps[ver-1], l)
    print(max(j for i, j in dp.items() if i<=l))