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
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:
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]
        #print(vv, ww)

        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])
        #print(dp)
            
        v//=2
        #k+=1
    print(dp[-1])

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())
    numbers = []
    while v != 0:
        numbers.append(v)
        v //= 2
    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:
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
        Ans[q] = sorted(knap, reverse = True)[0][0]

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product
from bisect import bisect_right


def main():
    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)


if __name__ == "__main__":
    main()

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
    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:
N = int(input())

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

Q = int(input())

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

L_max = 10 ** 5 + 1

nap_dic = {0: [0] * L_max}

for vL in vL_array:
    v, L = vL
    v_len = len(bin(v)) - 2
    for shift in range(v_len - 1, 0, -1):
        vv = v >> shift
        if vv in nap_dic:
            continue
        else:
            nap_dic[vv] = [max(nap_dic[vv // 2][i], nap_dic[vv // 2][i - vw_array[vv - 1][1]] + vw_array[vv - 1]
                               [0]) if vw_array[vv - 1][1] <= i else nap_dic[vv // 2][i] for i in range(L_max)]
    if L >= vw_array[v - 1][1]:
        ans = max(nap_dic[v // 2][L], nap_dic[v // 2]
                  [L - vw_array[v - 1][1]] + vw_array[v - 1][0])
    else:
        ans = nap_dic[v // 2][L]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import copy
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
d[min(lm,l[0][1])] = l[0][0]
dic[1] = d
def dfs(x):
    if x in dic:
        return dic[x]
    li = copy.deepcopy(dfs(x//2))
    for i in range(lm-1,-1,-1):
        if li[i] >= 0 and i+l[x-1][1] <= lm:
            s = i+l[x-1][1]
            li[s] = max(li[s],li[i]+l[x-1][0])
    dic[x] = li
    return li

for a,b in Q:
    s = dfs(a)
    print(max(s[:b+1]))

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)]
	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:
import sys
sys.setrecursionlimit(10**5)

def knapsack(ws, vs, limit, i):
  return 0 if i < 0 or limit == 0 else knapsack(ws, vs, limit, i-1) if ws[i] > limit else max(knapsack(ws, vs, limit-ws[i], i-1)+vs[i], knapsack(ws, vs, limit, i-1))

from collections import deque
N = int(input())
VW = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
for _ in range(Q):
  v, L = map(int, input().split())
  vals = deque()
  weis = deque()
  x = v
  while x > 0:
    vals.append(VW[x-1][0])
    weis.append(VW[x-1][1])
    x //= 2
  print(knapsack(weis, vals, L, len(vals)-1))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
def rooting(index):
  targets = []
  while index > 0:
    targets.append(index)
    index = index // 2
  return targets

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:
            targets = rooting(data)
            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
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 = rooting(index)
  num = 1
  cn = tree.root
  items = [[cn.value, cn.weight]]
  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:
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
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_w = min(max_w, 10**5, max_q_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]
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())
vlist=[]
for i in range(n):
  a=input().split()
  vlist.append([int(a[0]),int(a[1])])
  
def ans(v0,limit):
  if v0==0:
    return 0
  elif limit<=0:
    return 0
  else:
    v0v=vlist[v0-1][0]
    v0w=vlist[v0-1][1]
    ue=math.floor(v0/2)
    a1=ans(ue,limit)
    if limit<v0w:
      return a1
    else:
      a2=ans(ue,limit-v0w)+v0v
      return max([a1,a2])

q=int(input())
for i in range(q):
  b=input().split()
  v1=int(b[0])
  l1=int(b[1])
  print(ans(v1,l1))

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N = int(input())
    l = []
    for _ in range(N):
        v, w = map(int, input().split())
        l.append((v, w))
    Q = int(input())
    dp = {}
    t = set()
    t.add(l[0])
    dp[1] = t
    ll = []
    for _ in range(Q):
        v, L = map(int, input().split())
        ll.append((v, L))
    l2 = copy.deepcopy(ll)
    l2.sort()
    def make(i):
        if i in dp:
            return
        if int((i)/2) in dp:
            t = copy.deepcopy(dp[(int(i/2))])
            for j in dp[int(i/2)]:
                if l[i-1][1] + j[1] > 10**5:
                    continue
                t.add((j[0]+l[i-1][0], j[1]+l[i-1][1]))
            t.add(l[i-1])
            dp[i] = t
        else:
            make(int(i/2))
            make(i)
    for i, v in l2:
        make(i)
    for i in range(Q):
        v, L = ll[i]
        m = 0
        for i in dp[v]:
            if i[1] <= L:
                m = max(m, i[0])
        print(m)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
M = 10 ** 5 + 1
K = 9
A = [(0, 0)] * max(N + 1, 1 << K)
X = [[], [-1] * M]
X[1][0] = 0
v, w = map(int, input().split())
X[1][w] = v
A[1] = (v, w)
for i in range(2, min(N + 1, 1 << K)):
    v, w = map(int, input().split())
    if i % 2 == 0:
        X.append(X[i // 2][:])
    else:
        X.append([])
        X[i] = X[i // 2]
    
    for j in range(w, M)[::-1]:
        if X[i][j-w] >= 0:
            X[i][j] = max(X[i][j], X[i][j-w] + v)
    
    A[i] = (v, w)

for i in range(1 << K, N + 1):
    v, w = map(int, input().split())
    A[i] = (v, w)

if len(X) < 1 << K:
    for i in range(len(X), 1 << K):
        X.append([-1] * M)

for i in range(1 << K - 1, 1 << K):
    for j in range(1, M):
        X[i][j] = max(X[i][j], X[i][j-1])

Q = int(input())
for _ in range(Q):
    i, maw = map(int, input().split())
    if i < 1 << K - 1:
        V = []
        W = []
        while i:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        k = len(V)
        ma = 0
        for i in range(1 << k):
            ww = sum([w for j, w in enumerate(W) if i >> j & 1])
            if ww <= maw:
                ma = max(ma, sum([v for j, v in enumerate(V) if i >> j & 1]))
        print(ma)
    else:
        V = []
        W = []
        while i >= 1 << K:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        k = len(V)
        ma = 0
        for i in range(1 << k):
            ww = sum([w for j, w in enumerate(W) if i >> j & 1])
            if ww > maw: continue
            vv = sum([v for j, v in enumerate(V) if i >> j & 1])
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Time Limit Exceeded

Solution code:
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)
    
  print(max([tmp[0] for tmp in dp]))

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)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    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

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v = (v - 1) // 2
        flag[v] = True


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 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)
    #print(sosen_list)
    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())

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

for i in range(min(2**9, 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**9:
        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:
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 = defaultdict(lambda: 10**7)
    dp[0] = 0
    for v, w in nums:
        for nv, nw in list(dp.items()):
            if nw + w <= l:
                dp[nv + v] = min(dp[nv + v], nw + w)
    print(max(dp))

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)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    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

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v //= 2
        flag[v] = True


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 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 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] = [-1] * size
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])
            for k in range(len(temp) - w0):
                p = len(temp) - k - w0 - 1
                q = len(temp) - k - 1
                if temp[p] != -1:
                    temp[q] = max(temp[q], temp[p] + v0)
            status[j] = temp
        else:
            pass
    temp2 = status[v][:l + 1]
    print(max(temp2))

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())
vL = [list(map(int,input().split())) for i in range(Q)]
vs,Ls = zip(*vL)

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = sorted(list(set(appear)))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL + 2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        V,W = VW[ns]
        s = dic[s]
        ns = dic[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[orgv][L])

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

N = int(input())
VW = tuple(tuple(map(int, input().split())) for _ in range(N))
q = int(input())

def main():
    def f(x, W):
        S = []
        b = x.bit_length()
        for j in range(b):
            S.append(VW[(x>>j)-1])
        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[:b//2])
        T1 = make(S[b//2:])

        # 2つの全列挙を元に解を求める
        return max(solve(T0, T1))

    for _ in range(q):
      x, l = map(int, input().split())
      ans = f(x, l)
      print(ans)
if __name__ == "__main__":
  main()