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:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

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

#print(vw)
A = 12
N = min(1<<A,n+1)
memo = [[(0,0)] for _ in range(N)]


memo[1].append((vw[1][1],vw[1][0]))

for i in range(2,N):
    v,w = vw[i]
    m2 = [(w+w1,v+v1) for w1,v1 in memo[i>>1]]
    
    idx = 0
    L = len(m2)
    for (w,v) in memo[i>>1][1:]:
        while m2[idx][0] < w and idx < L:
            w2,v2 = m2[idx]
            memo[i].append((w2,max(v2,memo[i][-1][1])))
            idx += 1
        memo[i].append((w,max(v,memo[i][-1][1])))
    for w,v in m2[idx:]:
        memo[i].append((w,max(v,memo[i][-1][1])))
        
#print(memo)

    #memo[i] = memo[i>>1] + [(w+w1,v+v1) for w1,v1 in memo[i>>1]]

#print(memo)

"""
for i in range(1,N):
    memo[i].sort()
    L = len(memo[i])
    for j in range(1,L):
        I,J = memo[i][j]
        if J >= memo[i][j-1][1]:
            memo[i][j] = (I,J)
"""    
        
from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    #print(lst)
    for w,v in dic:
        idx = bisect_left(lst, (l+1-w,0))-1
        if idx >= 0 and v+lst[idx][1] > ans:
            ans = v+lst[idx][1]
    print(ans)        




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

    dic = [(0,0)]
    while u >= N:
        v,w = vw[u]
        dic += [(w+w1,v+v1) for w1,v1 in dic]
        u >>= 1
    
    solve(memo[u],dic,l)

Submission status: Time Limit Exceeded

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

# In[2]:


import math


# 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[10]:


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

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


# In[ ]:

Submission status: Time Limit Exceeded

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

N = int(input())

V = [0]
W = [0]

for i in range(N):
    vi, wi = list(map(int, input().split()))
    V.append(vi)
    W.append(wi)

Q = int(input())

v = []
L = []

for i in range(Q):
    vi, li = list(map(int, input().split()))
    v.append(vi)
    L.append(li)


# Lmax = max(L)

# dp = [[] * Lmax for _ in range(N)]


# for i in range(N):
#     for j in range(Lmax):
#         dp[i][j] = -1

# for i in range(Lmax):
#     dp[0][i] = 0

# def find(dp, v, l):
#     if dp[v][l] == -1:
#         if W[v] > L:
#             dp[v][l] = find(dp, v//2, l)
#         else:
#             dp[v][l] = max(find(dp, v//2, l), find(dp, v//2, l - W[v]))

#     return dp[v][l]

def find(v, l):
    if v == 0:
        if l <= W[0]:
            return V[0]
        else:
            return 0
    else:
        if W[v] > l:
            return find(v//2, l)
        else:
            return max(find(v//2, l), find(v//2, l - W[v]) + V[v])



for j in range(Q):
    print(find(v[j], L[j]))

Submission status: Time Limit Exceeded

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

need = [0] * (N + 1)
for v, l in vL:
    while v != 0 and need[v] < l:
        need[v] = l
        v //= 2

dp = [None for _ in range(N + 1)]
dp[0] = [0] * (need[1] + 1)

for i, (v, w) in enumerate(VW):
    me = i + 1
    if need[me] == False:
        continue
    parent = (me) // 2
    dp[me] = dp[parent][:w]
    for j in range(w, (need[1] + 1)):
        dp[me].append(max(dp[parent][j - w] + v, dp[parent][j]))

for v, l in vL:
    print(dp[v][l])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
VW=[list(map(int,input().split())) for i in range(n)]
q=int(input())
vL=[list(map(int,input().split())) for i in range(q)]


for i in range(q):
    v,L=vL[i]
    dic={}
    dic[0]=0
    now=v
    for i in range(int(math.log2(v)+1)):
        # dic2={}
        # print(i)
        # print(dic.keys())
        for j in list(dic.keys()):
            V,W=VW[now-1]
            if j+W<=L:
                if not j+W in dic:
                    dic[j+W]=dic[j]+V
                else:
                    dic[j+W]=max(dic[j+W],dic[j]+V)
        now//=2
    # print(dic)
    tmp=list(dic.values())
    tmp.sort()
    print(tmp[-1])

Submission status: Time Limit Exceeded

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

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())),)
    return np.array(x)

N = int(input())
VW = int_mtx(N)
Q = int(input())
vL = int_mtx(Q)

for i in range(Q):
    v = vL[i,0]
    L = vL[i,1]
    Node = []
    while True:
        Node.append(v)
        if v == 1:
            break
        v = int(v/2)

    dp = np.zeros(L+1)
    for n in range(1,len(Node)+1):
        V = VW[Node[n-1]-1,0]
        W = VW[Node[n-1]-1,1]
        np.maximum(dp[:-W]+V, dp[W:], out=dp[W:])

    print(int(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    dic = {}
    q = int(input())
    Q = []
    lm = 0
    for i in range(q):
        a,b = map(int,input().split())
        lm = max(b,lm)
        Q.append((a,b))
    d = [-1]*(lm+1)
    d[0] = 0
    if l[0][1] <= lm:
        d[l[0][1]] = l[0][0]
    dic[1] = d
    def dfs(x):
        if x in dic:
            return dic[x]
        c = [-1]*(lm+1)
        v,w = l[x-1]
        li = dfs(x//2)
        for i in range(lm,-1,-1):
            c[i] = li[i]
            if li[i] >= 0 and i+w <= lm:
                c[i+w] = max(li[i+w],li[i]+v)
        dic[x] = c
        return c

    for a,b in Q:
        s = dfs(a)
        print(max(s[:b+1]))
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
import sys
input = sys.stdin.readline

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)]
#import numpy as np
#dp=np.full((n+1,10**5+1),-1,int)
dp=[[-1]*(10**5+1) for _ in range(n+1)]
#dp[:,0]=0
#dp[1,:vw[0][1]]=0
#dp[1,vw[0][1]:]=vw[0][0]
def func(i,l):
  if l==0:
    return 0
  if i==1:
    if l>=vw[0][1]:
      return vw[0][0]
    else:
      return 0
  if dp[i][l]>-1:
    return dp[i][l]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[i][w]=ret
  return ret
for v,l in vl:
  print(func(v,l))

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): 
				for vv in range(uu+1):
					dp[uu] = max(dp[uu], dp[vv] + prev[uu - vv])
			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(' '))
	f(v,10**5, h, mem)
	print mem[v][l]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
VW = []
for i in range(n):
    v, w = map(int, input().split())
    VW.append([v, w])
q = int(input())
for i in range(q):
    v, L = map(int, input().split())

    def f(m):
        while m != 0:
            yield m
            m //= 2
    numbers = f(v)
    ones = [VW[i - 1] for i in numbers]
    # print(ones)

    def dp(j, W):
        if j >= len(ones):
            return 0
        elif W - ones[j][1] < 0:
            return dp(j + 1, W)
        else:
            p1 = dp(j + 1, W)
            p2 = dp(j + 1, W - ones[j][1]) + ones[j][0]
            return max(p1, p2)
    p = dp(0, L)
    #print('the answer', end='')
    print(p)

Submission status: Time Limit Exceeded

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

# In[2]:


import math
import numpy as np


# 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[10]:


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

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


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**6


N = int(input())
VW = [(inf, inf)] + [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
d = {i + 1: [] for i in range(N)}


def rec(i):
    if len(d[i]) > 0:
        return d[i]
    if i == 1:
        vi, wi = VW[i]
        d[i] = [(0, 0), (wi, vi)]
        return d[i]
    tmp = []
    vi, wi = VW[i]
    for w, v in rec(i // 2):
        tmp.append((w, v))
        tmp.append((w + wi, v + vi))
    tmp.sort()

    m = 1
    for j in range(1, len(tmp)):
        if tmp[m - 1][1] < tmp[j][1]:
            tmp[m] = tmp[j]
            m += 1
    d[i].extend(tmp[:m])
    return d[i]


ans = [-1] * Q
for q in range(Q):
    n, L = map(int, input().split())
    wei, val = zip(*rec(n))
    i = bisect.bisect_right(wei, L) - 1
    ans[q] = val[i]

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

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
size = 100001
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:
                    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:
n=int(input())
vw=[]
for i in range(n):
    vi,wi=map(int,input().split())
    vw.append([vi,wi])
    
def rec(v,w):
    ans=0
    v2=v//2
    
    if v==0:
        return 0
    
    elif vw[v-1][1]>w:
        return rec(v2,w)
    
    else:
        ans=max(rec(v2,w),(rec(v2,w-vw[v-1][1])+vw[v-1][0]))
        return ans


q=int(input())
for i in range(q):
    vi,li=map(int,input().split())
    print(rec(vi,li))

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])
    print(dp[-2][-1])

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

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

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:
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**9:
    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**9) for _ in range(2**8)]
    for i in range(2**8, 2**9):
        for j in range(2**9):
            sumv, sumw = 0, 0
            for k in range(9):
                if (j >> k) & 1:
                    v, w = I[((i + 1) << k) - 1]
                    sumv += v
                    sumw += w
            T[i - 2**8][j] = (sumw, sumv)
        T[i - 2**8].sort()

    for _ in range(Q):

        u, L = map(int, input().split())
        if u < 2**9:
            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**9:
                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**9 and sw + T[u - 2**8][j][0] <= L:
                    tmp = max(tmp, T[u - 2**8][j][1])
                    j += 1
                res = max(res, sv + tmp)
            print(res)

Submission status: Time Limit Exceeded

Solution code:
# D 
import numpy as np

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

vL = np.array(vL).reshape(Q,2)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def branchAndBound(N: int, M: int, V: list, W: list, R: list) -> int:
    def upperbound(w, v, i):
        rest = M - w
        _v = v
        for j in range(i + 1, N):
            if W[j] >= rest:
                rest -= W[j]
                v += V[j]
                _v = v
            else:
                _v += R[j] * rest
                break
        return v, _v

    prov, tmp = upperbound(0, 0, -1)
    h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]

    while h:
        _v, w, v, cur = heappop(h)
        if _v > prov or cur == N - 1:

            continue
        nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
        if nxtw >= M:

            heappush(h, (_v, nxtw, nxtv, cur + 1))
        _prov, ub = upperbound(w, v, cur)
        if _prov < prov:

            prov = _prov
        if ub < prov:

            heappush(h, (ub, w, v, cur + 1))
    return -prov


def solve():
    n = ni()
    bag = [(v/w, -v, -w) for v, w in [tuple(nm()) for _ in range(n)]]
    q = ni()
    for _ in range(q):
        v, L = nm()
        l = list()
        while v:
            l.append(bag[v-1])
            v >>= 1
        l.sort(reverse=True)
        R = [x[0] for x in l]
        V = [x[1] for x in l]
        W = [x[2] for x in l]
        print(branchAndBound(len(R), -L, V, W, R))
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
VW = [lr() for _ in range(N)]
answer = [None] * (N+1)
dp = np.array([0] * (10 ** 5 + 1))

def dfs(dp, i):
    v, w = VW[i-1]
    next = dp.copy()
    next[w:] = np.maximum(dp[w:], dp[:-w] + v)
    answer[i] = next
    if 2 * i <= N:
        dfs(next, 2*i)
    if 2 * i + 1 <= N:
        dfs(next, 2*i+1)

dfs(dp, 1)
Q = ir()

for _ in range(Q):
    v, L = lr()
    print(answer[v][L])