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


#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])
    bb = BranchAndBound(Wparent,Vparent, L, [0 for _ in range(len(parent))] )
    ans = bb.breadthFirstSearch()
    print(str(int(ans)))

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:
            index = data
            targets = []
            while index > 0:
                targets.append(index)
                index = index // 2
            num = 1
            pn = n
            cn = n
            for i in reversed(targets[:-1]):
                if i == num * 2:
                    pn = cn
                    cn = cn.left
                else:
                    pn = cn
                    cn = cn.right
                num = i
            if targets[1] * 2 == targets[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()])

import math
height = math.ceil(math.log2(n))
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:
        p1 = knapsack(i+1, w)
        p2 = knapsack(i+1, w - items[i][1]) + items[i][0]
        if p1>p2:
            return p1
        else:
            return p2

for li in vl:
  index = li[0]
  targets = []
  while index > 0:
    targets.append(index)
    index = index // 2
  num = 1
  cn = tree.root
  items = [[cn.value, cn.weight]]
  end = targets[0]
  for i in reversed(targets[:-1]):
    if i == num * 2:
      cn = cn.left
    else:
      cn = cn.right
    num = i
    items.append([cn.value, cn.weight])
  print(knapsack(0, li[1]))

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 = [False] * (N + 1)
for v, _ in vL:
    while v != 0 and need[v] == False:
        need[v] = True
        v //= 2

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

for i, (v, w) in enumerate(VW):
    if need[i + 1] == False:
        continue
    parent = (i + 1) // 2
    dp[i + 1] = dp[parent][:w]
    for j in range(w, 100001):
        dp[i + 1].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 sys
input = sys.stdin.readline
n = int(input())
vw = [list(map(int,input().split())) for _ in range(n)]

def func(u,l):
  dvw = []
  while(u>0):
    if vw[u-1][1]<=l:
      dvw.append(vw[u-1])
    dvwl = len(dvw)
    u = u//2
  def dfs(num,v,w):
    if num >= dvwl:
      return v
    dv,dw = dvw[num]
    if w + dw <= l:
      return max(dfs(num+1,v,w),dfs(num+1,v+dv,w+dw))
    else:
      return dfs(num+1,v,w)
  print(dfs(0,0,0))
q = int(input())
for _ in range(q):
  u,l = map(int,input().split())
  func(u,l)

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 = 10
N = min(1<<A,n+1)
memo = [None for _ in range(N)]
memo[1] = {0:0,vw[1][1]:vw[1][0]}
for i in range(2,N):
    v,w = vw[i]
    memo[i] = memo[i>>1].copy()
    #print(i,memo)
    for w1,v1 in memo[i>>1].items():
        #print(v1,w1,v,w)
        if w+w1 in memo[i]:
            memo[i][w+w1] = max(memo[i][w+w1], v+v1)
        else:
            memo[i][w+w1] = v+v1

#print(memo)

for i in range(1,N):
    lst = [(0,0)]
    for k,v in sorted(memo[i].items()):
        lst.append((k,max(v,lst[-1][1])))
    memo[i] = lst

from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    for w,v in dic.items():
        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]
        ndic = dic.copy()
        for w1,v1 in dic.items():
            #print(v1,w1,v,w)
            if w+w1 in ndic:
                ndic[w+w1] = max(ndic[w+w1], v+v1)
            else:
                ndic[w+w1] = v+v1

        dic = ndic
        u >>= 1
    
    solve(memo[u],dic,l)

Submission status: Time Limit Exceeded

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

  dp={0:0}
  for i in range(len(weights)):
    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:
import math
N = int(input())
from collections import defaultdict
items = defaultdict(lambda: [] * 2)
C = defaultdict(lambda: defaultdict(int))
max_w = 0
for i in range(1,N+1):
  v,w = map(int,input().split())
  items[i] = [v,w]
  max_w += w
for i in range(1, N+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]
Q = int(input())
for i in range(Q):
  v, l = map(int,input().split())
  if l > max_w:
    l = max_w
  print(C[v][l])

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ans=[]
    ans.append(0)
    
    from collections import defaultdict
    dd = defaultdict(int)
    dd[0]=0
    v,w=MI()
    dd[w]=v
    ans.append(dd)
    
    for i in range(2,N+1):
        v,w=MI()
        pdd=ans[i//2]
        dd = defaultdict(int)
        Lv=[]
        Lw=[]
        for k,vv in pdd.items():
            Lv.append(vv)
            Lw.append(k)
            dd[k]=vv
        for j in range(len(Lv)):
            nw=Lw[j]+w
            if nw<=100000:
                dd[nw]=max(dd[nw],Lv[j]+v)
        ans.append(dd)
                
    
    
    Q=I()
    for i in range(Q):
        v,Li=MI()
        temp=0
        for k,vv in ans[v].items():
            if k<=Li:
                temp=max(temp,vv)
                
        print(temp)
        
    
        

main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N=int(input())
maxL=10**5
items=[0]*(N+1)
v,w=map(int,input().split())
items[1]=[-1]*(maxL+1)
items[1][0]=0
items[1][w]=v
for i in range(2,N+1):
    v,w=map(int,input().split())
    predp=copy.copy(items[i//2])
    for j in range(maxL,w-1,-1):
        if predp[j-w]>-1:
            predp[j]=max(predp[j],predp[j-w]+v)
    items[i]=predp

Q=int(input())
for _ in range(Q):
    v,L=map(int,input().split())
    print(max(items[v][:L+1]))

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[4]:


def knapsack(data,W):
    N = len(data)
    weight = [item[1] for item in data]
    value = [item[0] for item in 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 weight[i]<=w: #dp[i][w-weight[i]の状態に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]


# In[5]:


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[6]:


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


# In[ ]:

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
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict

N = int(input())
VW = [[0, 0]] + [[int(i) for i in input().split()] for _ in range(N)]
Q = int(input())
vL = [[int(i) for i in input().split()] for _ in range(Q)]
# schedule = defaultdict(lambda: [])
# for i, (v, L) in enumerate(vL) :
  # schedule[v].append((i, L))
  
def solve(N, W, ws, vs):
  *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))
  
for v, L in vL :
  ws, vs = [], []
  c = 0
  while v != 0 :
    ws.append(VW[v][1])
    vs.append(VW[v][0])
    v //= 2
    c += 1
  print(solve(c, L, ws, vs))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
v=list()
w=list()
dp=list()
for i in range(n):
    a,b=map(int,input().split())
    v.append(a)
    w.append(b)
q=int(input())

def dp(V,L):
    if L<0:
        return(-10000000)
    elif V==1:
        if w[0]<=L:
            return(v[0])
        else:
            return(0)
    else:
        return(max(dp(V//2,L),dp(V//2,L-w[V-1])+v[V-1]))
    
res=list()
for i in range(q):
    u,l=map(int,input().split())
    res.append(dp(u,l))
    
for i in res:
    print(i)

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 = [None for _ in range(N)]
memo[1] = {0:0,vw[1][1]:vw[1][0]}
for i in range(2,N):
    v,w = vw[i]
    memo[i] = memo[i>>1].copy()
    #print(i,memo)
    for w1,v1 in memo[i>>1].items():
        #print(v1,w1,v,w)
        if w+w1 in memo[i]:
            memo[i][w+w1] = max(memo[i][w+w1], v+v1)
        else:
            memo[i][w+w1] = v+v1

#print(memo)

for i in range(1,N):
    lst = [(0,0)]
    for k,v in sorted(memo[i].items()):
        lst.append((k,max(v,lst[-1][1])))
    memo[i] = lst

from bisect import bisect_left
def solve(lst,dic,l):
    ans = 0
    #print(lst,l)
    for w,v in dic.items():
        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]
        ndic = dic.copy()
        for w1,v1 in dic.items():
            #print(v1,w1,v,w)
            if w+w1 in ndic:
                ndic[w+w1] = max(ndic[w+w1], v+v1)
            else:
                ndic[w+w1] = v+v1

        dic = ndic
        u >>= 1
    
    solve(memo[u],dic,l)

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**9)

def main():
    n = int(ipt())
    data = [(0,0)]
    for _ in range(n):
        v,w = map(int,ipt().split())
        data.append((v,w))
    q = int(ipt())
    dp = [[0]*(10**5+1) for _ in range(n+1)]
    dpd = [-1]*(n+1)
    dpd[0] = 1

    def solve(i):
        if dpd[i//2] == -1:
            dp[i//2] = solve(i//2)
            dpd[i//2] = 1
        dpp = dp[i//2]
        dpn = [0]*(10**5+1)
        vi,wi = data[i]
        for j in range(10**5+1):
            if j < wi:
                dpn[j] = dpp[j]
            else:
                if dpp[j] < dpp[j-wi]+vi:
                    dpn[j] = dpp[j-wi]+vi
                else:
                    dpn[j] = dpp[j]
        return dpn

    for _ in [0]*q:
        v,l = map(int,ipt().split())
        print(solve(v)[l])

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f

def make_next(n, nums):
    imos = [0 for i in range(n)]
    for i, num in enumerate(nums):
        if num > i:
            imos[0] += 1
        else:
            imos[i - num] += 1

        if i + num + 1 < n:
            imos[i+num+1] -= 1
    # print(imos)
    nx = []
    tmp = 0
    for im in imos:
        tmp += im
        nx.append(tmp)

    return nx

def mantan_check(n, nums):
    if sum(nums) == n ** 2:
        return True
    else:
        return False
def knapsack(tree, vx, l):
    dp = [0 for i in range(l + 1)]
    while True:
        dpcp = copy.copy(dp)
        v, w = tree[vx-1]
        # print(v, w)
        for i, d in enumerate(dp):
            if w + i < l + 1:
                if dpcp[w + i] < v + d:
                    dpcp[w + i] = v + d
        dp = copy.copy(dpcp)
        vx //= 2
        dp = dpcp
        # print(dp)
        if vx == 0:
            break

    return max(dp)

def solve():
    n = getN()
    tree = []
    for i in range(n):
        tree.append(getList())

    Q = getN()
    for i in range(Q):
        v, l = getList()
        print(knapsack(tree, v, l))




def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

"""
5 10000000000000
4 0 0 0 0
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [list(map(int,input().split())) for _ in range(n)]

def func(u,l):
  dvw = []
  while(u>0):
    dvw.append(vw[u-1])
    dvwl = len(dvw)
    u = u//2
  def dfs(num,v,w):
    if num >= dvwl:
      return v
    dv,dw = dvw[num]
    if w + dw <= l:
      return max(dfs(num+1,v,w),dfs(num+1,v+dv,w+dw))
    else:
      return dfs(num+1,v,w)
  print(dfs(0,0,0))
q = int(input())
for _ in range(q):
  u,l = map(int,input().split())
  func(u,l)

Submission status: Time Limit Exceeded

Solution code:
def solved(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))

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 v,l in vl:
    ws = []
    vs = []
    while v:
        V,W = vw[v-1]
        ws.append(W)
        vs.append(V)
        v//=2
    ans = solved(len(ws),l,ws,vs)
    print(ans)

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))
for i in range(1,N+1):
  v,w = map(int,input().split())
  items[i] = [v,w]
for i in range(1, N+1):
  oya = math.floor(i/2)
  for w in range(1, 10**5+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]
Q = int(input())
for i in range(Q):
  v, l = map(int,input().split())
  print(C[v][l])

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

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 qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n:
        dfs(v * 2 + 2, depth + 1)


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

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)]
    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        knap = set()
        knap |= {(0, 0)}
        while v >= 1:
            nextK = set()
            val, weight = B[v-1]
            for item in knap:
                if item[1] + weight <= L: nextK |= {(val + item[0], weight + item[1])}
            knap |= nextK
            v //= 2
        maxV = 0
        for item in knap: maxV = max(maxV, item[0])
        Ans[q] = maxV

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:

def main():
  n = int(input())
  tree = [None] * (n + 1)
  tree[0] = [[0, 0]]

  for i in range(1, n + 1):
    v, w = map(int, input().split())
    prev = tree[i // 2]
    tree[i] = prev + [(vt + v, wt + w) for vt, wt in prev]

  q = int(input())
  for _ in range(q):
    v, l = map(int, input().split())
    print(max([vt for vt, lt in tree[v] if lt <= l]))


main()

Submission status: Time Limit Exceeded

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

n = int(input())

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

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

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