Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Time Limit Exceeded

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

N = int(input())
LIMIT = min(N,8195)

V = [0] * N
W = [0] * N
for i in range(N):
    nV, nW = map(int, input().split())
    V[i] = nV
    W[i] = nW

pre = [[] for i in range(LIMIT)]

for i in range(LIMIT):
    if i == 0:
        pre[i] = [(0,0), (W[i], V[i])]
        continue

    curr = pre[i]
    prev = pre[(i - 1)//2]
    nV, nW = V[i], W[i]
    
    size = len(prev)

    left = 0
    right = 0
    while left < size or right < size:
        if left == size or prev[left][0] > prev[right][0] + nW or (prev[left][0] == prev[right][0] + nW and prev[left][1] < prev[right][1] + nV):
            if len(curr) == 0 or prev[right][1] + nV > curr[-1][1]:
                curr.append((prev[right][0] + nW, prev[right][1] + nV))
            right += 1
        else:
            if len(curr) == 0 or prev[left][1] > curr[-1][1]:
                curr.append(prev[left])
            left += 1
Q = int(input())
out = [0] * Q
for t in range(Q):
    vert, L = map(int, input().split())
    vert -= 1

    stack = []
    while vert >= LIMIT:
        stack.append((V[vert], W[vert]))
        vert = (vert - 1) // 2
        
    prev = pre[vert]
    best = 0
    
    for i in range(1 << len(stack)):
        sV = 0
        sW = 0
        red = i
        for nV, nW in stack:
            if red & 1:
                sV += nV
                sW += nW
            red >>= 1

        limit = L - sW
        if limit < 0:
            continue
        
        lo = -1
        hi = len(prev)
        while hi - lo > 1:
            test = (hi + lo) // 2
            if prev[test][0] <= limit:
                lo = test
            else:
                hi = test
                
        if lo >= 0:
            new = prev[lo][1] + sV
            best = max(best, new)
        
    out[t] = best

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

Submission status: Time Limit Exceeded

Solution code:
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)]
for vLi in vL:
    vi = vLi[0]
    Li = vLi[1] 
    stock = [(VW[vi-1][0],VW[vi-1][1])]
    while vi != 1:
        vi = vi//2
        stock.append((VW[vi-1][0],VW[vi-1][1]))
    n = len(stock)
    V = [0 for _ in range(Li+1)]
    for vi,wi in stock:
        for l in range(1,Li+1)[::-1]:
            if l >= wi:
                V[l] = max(V[l],V[l-wi] + vi)
            else:
                V[l] = V[l]
    print(V[-1])

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_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
flag = [False] * n
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    v_to_qi[v].append(i)
    v_to_l[v].append(l)
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True

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


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

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    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 numpy as np
#from pandas import DataFrame
import copy

class BranchAndBound:
    def __init__(self, weights, values, max_weight, answer_val):
        self.weights = np.array(weights)
        self.values = np.array(values)
        self.max_weight = max_weight
        self.answer_val = answer_val
        self.evaluates = self.values/self.weights
        self.index_list = []
        for index in range(1, len(weights) + 1):
#            self.index_list.append('x' + str(index))
             self.index_list.append(int(index)-1)
#        self.target_df = DataFrame(np.c_[self.evaluates, self.weights, self.values, np.array(self.answer_val)], index=self.index_list, columns=["evaluate", "weight", "value", "ans"])
#        self.target_df = self.target_df.sort_values('evaluate', ascending=False)
#        self.answer_val = list(self.target_df['ans']) #　answer_val　を評価値の高い順にソートされたものに変更
#        del self.target_df['ans'] # DataFrameにはもう必要ないので「ans」カラムを削除
        self.target_array = np.c_[self.evaluates, self.weights, self.values, np.array(self.answer_val)]
        self.target_array = self.target_array[np.argsort(self.target_array[:,0])[::-1],:]
        self.answer_val = self.target_array[:,3].tolist() #　answer_val　を評価値の高い順にソートされたものに変更
        self.target_array = self.target_array[:,:3]
        
        self.target_ans = np.dot(np.array(answer_val), values)
#        self.index_list = self.target_df.index #indexの順番変更
        self.index_list = np.argsort(self.target_array[:,0])[::-1] #indexの順番変更

    def __judgeValue(self, fixed_list): # fixed_listで渡されたxの固定値における緩和問題を解き、分岐継続を判定する。また、よりよい解が見つかれば暫定解の交換を行う。
        sum_weight = 0 # 採択したxのweightの合計値
        evaluate_list = [] # 採択の判定を格納
        evaluate_list.extend(fixed_list)
        for index, val in enumerate(fixed_list):
            sum_weight += self.target_array[self.index_list[index],1]*val #  fixed_listで渡されたxの値でのweightの合計値

        for index in range(len(fixed_list), len(self.index_list)):
            if sum_weight > self.max_weight: #max_weightを超えた場合は分岐終了
                return False # 分岐終了
            elif sum_weight == self.max_weight: #max_weightに達しているので他のxは0
                evaluate_list.append(0)
                continue
            else:
                if sum_weight + self.target_array[self.index_list[index],1] < self.max_weight: # x=1にしてもmax_weightに到達しないとき
                    sum_weight += self.target_array[self.index_list[index],1]
                    evaluate_list.append(1)
                else: # 0 < x <= 1 となるとき
                    evaluate_list.append((self.max_weight - sum_weight)/self.target_array[self.index_list[index],1])
                    sum_weight = self.max_weight
                    if (self.max_weight - sum_weight) == self.target_array[self.index_list[index],1]: # x=1のとき、暫定解を入れ替える
                        evaluate_list_count = len(evaluate_list)
                        for i in range(evaluate_list_count, len(self.index_list)): # 決まっていないxは全部0を入れる
                            evaluate_list.append(0)
                        self.target_ans = np.dot(np.array(evaluate_list), self.target_array[:,2]) # 暫定解 target_ansの入れ替え　
                        self.answer_val = evaluate_list # 暫定解 answer_valの入れ替え
                        return False # 分岐終了

        if len(fixed_list) == len(self.index_list): # 全てのxの値が固定されているとき 暫定解との比較
            if (sum_weight <= self.max_weight) and (np.dot(np.array(fixed_list), self.target_array[:,2]) > self.target_ans): # 暫定解との比較
                self.target_ans = np.dot(np.array(fixed_list), self.target_array[:,2]) # 暫定解 target_ansの入れ替え　
                self.answer_val = fixed_list # 暫定解 answer_valの入れ替え
            return False

        if np.dot(np.array(evaluate_list), self.target_array[:,2]) > self.target_ans: # 緩和問題の解が暫定解を超えた時
            return True # 分岐継続
        else: # 暫定解を超えていないとき
            return False # 分岐終了 

    def breadthFirstSearch(self): #幅優先探索
        search_lists = [[0], [1]] # 要素 [0]、[1]は先に入れておく
        while len(search_lists) != 0: # search_listsが空になるまで続ける
            first_list = search_lists[0] # Queueで考える、上から１つ取得
            search_lists.pop(0) # 取得した要素は削除
            if self.__judgeValue(first_list): # 探索が継続かどうか
                new_list_cp = copy.deepcopy(first_list) # 次要素に「1」を追加するために深いコピー
                new_list_cp.append(0) # 0を末尾に追加
                search_lists.append(new_list_cp) # 新たな要素を search_listsの末尾に格納
                new_list_cp = copy.deepcopy(first_list) # 次要素に「0」を追加するために深いコピー
                new_list_cp.append(1) # 1を末尾に追加
                search_lists.append(new_list_cp) # 新たな要素を　search_listsの末尾に格納

#        print("-----幅優先探索-----")
#        for index, val in enumerate(self.index_list):
#            print(val + ": " + str(self.answer_val[index]))
#        print("ans: " + str(self.target_ans))
        return int(self.target_ans+0.1)
        

    def depthFirstSearch(self): #深さ優先探索
        search_lists = [[0], [1]] # 要素 [0]、[1]は先に入れておく
        while len(search_lists) != 0: # search_listsが空になるまで続ける
            first_list = search_lists[0] # Stachで考える、上から１つ取得
            search_lists.pop(0) # 取得した要素は削除
            if self.__judgeValue(first_list): # 探索が継続かどうか
                new_list_cp = copy.deepcopy(first_list) # 次要素に「1」を追加するために深いコピー
                new_list_cp.append(1) # 1を末尾に追加
                search_lists.insert(0, new_list_cp) # 新たな要素を search_listsの先頭に格納
                new_list_cp = copy.deepcopy(first_list) # 次要素に「0」を追加するために深いコピー
                new_list_cp.append(0) # 0を末尾に追加
                search_lists.insert(0, new_list_cp) # 新たな要素を　search_listsの先頭に格納

#        print("-----深さ優先探索-----")
#        for index, val in enumerate(self.index_list):
#            print(val + ": " + str(self.answer_val[index]))
#        print("ans: " + str(self.target_ans))
        return int(self.target_ans+0.1)


def Parent(v):
    parent = [v]
    c = v
    while c>1:
        p = int((c+0.1)//2)
        parent.append(p)
        c = p
    return parent

def greedy(weights, values, max_weight):
    eva = values/weights
    eva_sort = np.argsort(eva)[::-1]
    eva_sort = eva_sort.tolist()
    now_weight = 0
    ans = [0 for _ in range(len(weights))]
    ans_val = 0
    for j in eva_sort:
        if now_weight+weights[j] <= max_weight:
            ans[j] = 1
            ans_val+=values[j]
            now_weight+= weights[j]
    return ans

#f = open('./input_D.txt')
#N = int(f.readline())
N = int(input())
V = []
W = []
for i in range(N):
#    Vi,Wi = map(int, f.readline().split())
    Vi,Wi = map(int, input().split())
    V.append(Vi)
    W.append(Wi)
    
#Q = int(f.readline())
Q = int(input())
for i in range(Q):
#    v,L = map(int, f.readline().split())
    v,L = map(int, input().split())
    parent = Parent(v)
    Vparent = []
    Wparent = []
    for p in parent:
        Vparent.append(V[p-1])
        Wparent.append(W[p-1])
    greed_ans = greedy(np.array(Wparent),np.array(Vparent),L)
#    bb = BranchAndBound(Wparent,Vparent, L, [0 for _ in range(len(parent))])
    bb = BranchAndBound(Wparent,Vparent, L, greed_ans)
    ans = bb.breadthFirstSearch()
#    ans = bb.depthFirstSearch()
    print(str(int(ans)))

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
mem = {}
h = [None for _ in range(n + 1)]
for u in range(n):
	v, w = map(int,raw_input().split(' '))
	h[u + 1] = (v,w)
nq = int(raw_input())
def f(v,l,h,mem):
	dp = [0 for _ in range(l+1)]
	if v in mem:
		return mem[v][l]
	ov = v
	while(v):
		cv, cw = h[v]
		if v in mem:
			m = 0
			prev = mem[v]
			for uu in range(l+1): m = max(dp[uu] + prev[l - uu], m)
			return m
			v = 0
		else:
			for ww in range(l,-1,-1):
				if ww - cw >= 0: 
					dp[ww] = max(dp[ww], dp[ww - cw] + cv)
				else:
					break
		v = v/2
	mem[ov] = dp
	return dp[l]
res = []
for _ in range(nq):
	v,l = map(int, raw_input().split(' '))
	res.append((v,l))
	f(v,10**5, h, mem)
for v,l in res:
	print f(v,l,h,mem)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
V=[]
W=[]
for i in range(n):
  v,w=map(int,input().split())
  V.append(v)
  W.append(w)
q=int(input())
for _ in range(q):
  v,l=map(int,input().split())
  s=v
  weights=[]
  values=[]
  z=0
  while s>=1:
    z+=1
    weights.append(W[s-1])
    values.append(V[s-1])
    s=s//2

  dp={0:0}
  for i in range(z):
    w=weights[i]
    val=values[i]
    dplist=list(dp.keys())
    for c in dplist:
      p=c+w
      v=dp[c]+val
      if p in dp and dp[p]>v:
        continue
      else:
        dp[p]=v

  v=0
  for c in dp:
    x=dp[c]
    if c<=l and x>v:
      v=x
  print(v)

Submission status: Time Limit Exceeded

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

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

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


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

    if len(v_to_qi[v]) > 0:
        for i in range(len(v_to_qi[v])):
            ans[v_to_qi[v][i]] = dp[depth + 1][v_to_l[v][i]]

    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:
N = int(input())
V = [None]*N
W = [None]*N

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

Q = int(input())


for q in range(Q):
    v, L = map(int, input().split())
    
    sosen = set()
    t = v
    while t != 1:
        sosen.add(t)
        t = int(t/2)
    sosen.add(1)
    sosen_list = list(sosen)
    dp = [[0]*(L+1) for i in range(len(sosen_list)+1)]

    for i in range(len(sosen_list)):
        for j in range(L+1):
            if j < W[sosen_list[i]-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[sosen_list[i]-1]]+V[sosen_list[i]-1])
    MAX = 0
    for d in dp:
        MAX = max(MAX, max(d))
    print(MAX)

Submission status: Time Limit Exceeded

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

N = int(input())
LIMIT = min(N,2047)

V = [0] * N
W = [0] * N
for i in range(N):
    nV, nW = map(int, input().split())
    V[i] = nV
    W[i] = nW

pre = [[] for i in range(LIMIT)]

for i in range(LIMIT):
    if i == 0:
        pre[i] = [(0,0), (W[i], V[i])]
        continue

    curr = pre[i]
    prev = pre[(i - 1)//2]
    nV, nW = V[i], W[i]
    
    size = len(prev)

    left = 0
    right = 0
    while left < size or right < size:
        if left == size or prev[left][0] > prev[right][0] + nW or (prev[left][0] == prev[right][0] + nW and prev[left][1] < prev[right][1] + nV):
            if len(curr) == 0 or prev[right][1] + nV > curr[-1][1]:
                curr.append((prev[right][0] + nW, prev[right][1] + nV))
            right += 1
        else:
            if len(curr) == 0 or prev[left][1] > curr[-1][1]:
                curr.append(prev[left])
            left += 1
Q = int(input())
out = [0] * Q
for t in range(Q):
    vert, L = map(int, input().split())
    vert -= 1

    stack = []
    while vert >= LIMIT:
        stack.append((V[vert], W[vert]))
        vert = (vert - 1) // 2
        
    prev = pre[vert]
    best = 0
    
    for i in range(1 << len(stack)):
        sV = 0
        sW = 0
        red = i
        for nV, nW in stack:
            if red & 1:
                sV += nV
                sW += nW
            red >>= 1

        limit = L - sW
        if limit < 0:
            continue
        
        lo = -1
        hi = len(prev)
        while hi - lo > 1:
            test = (hi + lo) // 2
            if prev[test][0] <= limit:
                lo = test
            else:
                hi = test
                
        if lo >= 0:
            new = prev[lo][1] + sV
            best = max(best, new)
        
    out[t] = best

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_right


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:
                v, w = vw[li[cnt]]
                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(input())
vw = [(None, None)]
for _ in range(n):
    v, w = map(int, input().split())
    vw.append((v, w))
q = int(input())
ul = [map(int, input().split()) for _ in range(q)]

for u, l in ul:
    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)

    wv2 = [[key, val] for key, val in d2.items()]
    wv2.sort()
    for i in range(1, len(wv2)):
        w_now, v_now = wv2[i]
        w_pre, v_pre = wv2[i-1]
        if v_pre > v_now:
            wv2[i][1] = v_pre

    ans = 0
    for k1, v1 in d1.items():
        i = bisect_right(wv2, [l - k1 + 0.5, v1])
        ans = max(ans, wv2[i-1][1] + v1)

    print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())
ns = [0]
for i in range(n):
    v, w = map(int, input().split())
    ns.append((v, w))
q = int(input())
for i in range(q):
    v, l = map(int, input().split())
    nums = []
    while v != 1:
        nums.append(ns[v])
        v //= 2
    nums.append(ns[1])
    dp = [0] * (l + 1)
    for v, w in nums:
        for j in range(l, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    print(dp[l])

Submission status: Time Limit Exceeded

Solution code:
import heapq
#heapq.heapify(a)
#value=heapq.heappop(a)
#heapq.heappush(a, value)

def num2bi(x, k):
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
V=[0 for _ in range(N+1)]
W=[0 for _ in range(N+1)]
for i in range(N):
  v, w=input().split()
  V[i+1]=int(v)
  W[i+1]=int(w)
  
Q=int(input())
for i in range(Q):
  u, L=input().split()
  u=int(u)
  L=int(L)
  
  dp=[[0, 0]]
  while u>0:
    dptmp=list()
    for tmp in dp:
      cand=[tmp[0]-V[u], tmp[1]+W[u]]
      if cand[1]<=L:
        dptmp.append(cand)
    u//=2
    dp=dp+list(dptmp)
    
  heapq.heapify(dp)
  tmp=heapq.heappop(dp)
  print(-tmp[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
Vlist = []
Wlist = []
for _ in range(n):
    v, w = map(int, input().split())
    Vlist.append(v)
    Wlist.append(w)
    
q = int(input())

    
    
for j in range(q):
    v, l = map(int, input().split())

    dp = [0]*(l+1)
    k = 1   #行
    while v>=1:
        vv = Vlist[v-1]
        ww = Wlist[v-1]


        for z in reversed(range(1, l+1)):
            if z<ww:
                dp[z] = dp[z]
            elif z-ww>=0:
                dp[z] = max(dp[z-ww]+vv, dp[z])

            
        v//=2

    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
from collections import defaultdict
items = defaultdict(lambda: [] * 2)
C = defaultdict(lambda: defaultdict(int))
query = list()


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

max_q_w = 0
max_v = 0
Q = int(input())
for i in range(Q):
  v, l = map(int,input().split())
  query.append([v,l])
  max_q_w = max(max_q_w, l)
  max_v = max(max_v, v)


max_w = min(max_w, 10**5, max_q_w)


for i in range(1, max_v+1):
  oya = math.floor(i/2)
  for w in range(1, max_w+1):
    if items[i][1] <= w:
      prev = items[i][0] + C[oya][w-items[i][1]]
      best = C[oya][w]
      if prev > best:
        C[i][w] = prev
      else:
        C[i][w] = best
    else:
      C[i][w] = C[oya][w]
for v, l in query:
  if l > max_w:
    l = max_w
  print(C[v][l])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    X[i] = list(map(int, input().split()))
Q = int(input())
# query = [[] for _ in range(Q)]


for i in range(Q):
    # query[i] = list(map(int, input().split()))
    q = list(map(int, input().split()))

# for q in query:
    x = q[0]
    W = q[1]
    # w = []
    # v = []
    # print(int(math.log2(i)+1))
    size = int(math.log2(x)+1)
    i = size -1
    dp = [[0]*(W+1) for _ in range(size+1)]
    while x != 0:
        # v.append(X[x-1][0])
        # w.append(X[x-1][1])
        v, w = X[x-1]
        for j in range(W+1):
            if j < w:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w]+v)
        i -= 1
        x = x//2
    print(dp[0][W])
    
    # size = len(v)
    # dp = [[0]*(W+1) for j in range(size+1)]
    # for i in range(size-1,-1,-1):
    #     for j in range(W+1):
    #         if j < w[i]:
    #             dp[i][j] = dp[i+1][j]
    #         else:
    #             dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
    # print(dp[0][W])

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が最も高効率

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=max([qs[i][1] for i in range(Q)])

    dps=dict()
    dp=[0]*(maxL+1)
    v,w=costs[0]
    for wi in range(maxL,w-1,-1):
        dp[wi]=max(dp[wi-w]+v,dp[wi])

    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=copy(r(par))
        v,w=costs[n-1]
        for wi in range(maxL,w-1,-1):
            dp[wi]=max(dp[wi-w]+v,dp[wi])
        dps[n]=dp
        return dp
        
    for q in qs:
        v,L=q
        dp=r(v)

        print(dp[L])
        #print(dp)
    
   #print(dps[3][120])
        
        


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
  n = int(input())

  tree = [map(int, input().split()) for i in range(1, n + 1)]
  tree.insert(0, None)

  memo = [None] * (n + 1)
  memo[0] = [[0, 0]]


  def f(i):
    if memo[i]:
      return

    f(i // 2)
    prev = memo[i // 2]
    v, w = tree[i]
    memo[i] = sorted(
      prev + [(vt + v, wt + w) for vt, wt in prev],
      key=lambda tpl: -tpl[0]
    )


  for _ in range(int(input())):
    v, l = map(int, input().split())

    f(v)

    for vt, lt in memo[v]:
      if lt <= l:
        print(vt)
        break


main()

Submission status: Time Limit Exceeded

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

# In[2]:


import math
import numpy as np


# In[3]:


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


# In[7]:


def knapsack(data,W):
    N = len(data)
    
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i]=0

    #DP
    for i in range(N):
        for w in range(W+1):
            if data[i][1]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-data[i][1]]+data[i][0], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]


# In[8]:


def func(vw, v,l):
    mylist = [vw[v//(2**x)-1] for x in range(int(math.log2(v)+1))]
    
    ans = knapsack(mylist,l)
    print(ans)


# In[ ]:


for p in range(Q):
    v, l = map(int,input().split())
    func(vw, v, l)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
V = np.zeros(N, dtype=int)
W = np.zeros(N, dtype=int)
for n in range(N):
  V[n], W[n] = [int(x) for x in input().split(' ')]
Q = int(input())
X = np.zeros(Q, dtype=int)
L = np.zeros(Q, dtype=int)
for q in range(Q):
  X[q], L[q] = [int(x) for x in input().split(' ')]
  
DP = [None] * N  # max value when weight total is equal or less than index
M = 10 ** 5 + 5
def dp(x):
  if DP[x] is not None:
    return DP[x]
  if x == 0:
    prev = np.zeros(M, dtype=int)
  else:
    prev = dp((x+1)//2-1)
  DP[x] = np.concatenate((prev[:W[x]],
                         np.maximum(prev[(W[x]):],
                                    prev[:(M-W[x])] + V[x])))
  #print(x+1, DP[x][:15])
  return DP[x]
for x, l in zip(X, L):
  print(dp(x-1)[l])

Submission status: Time Limit Exceeded

Solution code:
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
dp = [[-1 for j in range(c+1)] for i in range(n+1)]
for i in range(c+1):
    dp[0][i] = 0
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, n+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]
    print(dp[vi][li])