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:
from heapq import heappush, heappop

def max_value(t, xs):
    def _cost(weight, value, i):
        for j in range(i, n):
            v, w = xs[j]
            if weight + w > t:
                return (-value, -value - (v/w)*(t-weight))
            weight += w
            value += v
        return (-value, -value*1.0)

    n = len(xs)
    xs.sort(key=lambda x: x[0]/x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if cost > maxcost:
            break
        if i < n:
            v, w = xs[i]
            if weight+w <= t:
                heappush(heap, (cost, upper, weight+w, value+v, i+1))
            u, c = _cost(weight, value, i+1)
            if c < maxcost:
                if u < maxcost:
                    maxcost = u
                heappush(heap, (c, u, weight, value, i+1))

    return -maxcost

N = int(input())

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

Q = int(input())

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(max_value(L, item))

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][1] * bit
            value += vwl[items[idx]-1][0] * bit
        if weight > l:
            continue
        ans = max(dp[v][l-weight]+value, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

import sys
input = sys.stdin.readline

N = int(input())
#tree = [[i * 2 + 1,i * 2 + 2] for i in range(N // 2)]
item = [[0,0] for i in range(N)]

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

def path(n):
  way = [n]
  if n == 1:
    return way
  else:
    while n > 1:
      n = n // 2
      way.append(n)
    return way[::-1]

for q in range(Q):
  edge,lim = map(int,input().split())
  P = path(edge)
  #print(P)
  total = 0
  dp = np.zeros(lim + 2)
  for j in range(len(P)):
    k = P[j] - 1
    value = item[k][0]
    weight = item[k][1]
    if weight > lim:
      continue
    dp[weight:] = np.maximum(dp[weight:],dp[:-weight] + value)
  print(int(dp[lim]))

Submission status: Time Limit Exceeded

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

n = int(input())

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

a = [[] for i in range(2**11)]

for i in range(1,min(n+1,2**11)):
    if i == 1:
        a[i].append((w[1],v[1]))
    else:
        p = i//2
        tank = set([(w[i],v[i])])
        for ww,vv in a[p]:
            tank.add((ww,vv))
            if ww + w[i] <= 10**5:
                tank.add((ww+w[i],vv+v[i]))
        tank = list(tank)
        tank.sort()
        ma = -1
        for j in range(len(tank)):
            ww,vv = tank[j]
            if vv > ma:
                if j == len(tank)-1 or tank[j+1][0] != ww:
                    ma = vv
                    a[i].append((ww,vv))



Q = int(input())
for _ in range(Q):
    now,L = map(int,input().split())
    if now < 2**11:
        if a[now][0][0] > L:
            print(0)
        else:
            ok = 0
            ng = len(a[now])

            while ng - ok > 1:
                mid = (ok+ng)//2
                if a[now][mid][0] > L:
                    ng = mid
                else:
                    ok = mid
            print(a[now][ok][1])
    else:
        pp = [(0,0)]
        while now >= 2**11:
            tank = []
            for ww,vv in pp:
                if ww+w[now] <= L:
                    tank.append((ww+w[now],vv+v[now]))
            for e in tank:
                pp.append(e)
            now = now//2
        
        res = 0

        for ww,vv in pp:
            L -= ww
            if a[now][0][0] > L:
                res = max(res,vv)
            else:
                ok = 0
                ng = len(a[now])

                while ng - ok > 1:
                    mid = (ok+ng)//2
                    if a[now][mid][0] > L:
                        ng = mid
                    else:
                        ok = mid
                res = max(res,a[now][ok][1] + vv)

            L += ww
        print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import product
    from operator import itemgetter
    n = int(input())
    vw = [list(map(int, readline().split())) for _ in range(n)]
    q = int(input())

    for _ in range(q):
        v, l = list(map(int, readline().split()))
        nap = []
        while v > 0:
            nap.append(vw[v - 1])
            v //= 2

        num = len(nap)

        nap_first = nap[:(num + 1) // 2]
        nap_second = nap[(num + 1) // 2:]

        set_first = []
        len_nf = len(nap_first)
        for bit in product(range(2), repeat=len_nf):
            cur_v = 0
            cur_w = 0
            for i in range(len_nf):
                if bit[i] == 1:
                    cur_v += nap_first[i][0]
                    cur_w += nap_first[i][1]
            set_first.append((cur_v, cur_w))

        if not set_first:
            set_first.append([0, 0])

        set_second = []
        len_ns = len(nap_second)

        for bit in product(range(2), repeat=len_ns):
            cur_v = 0
            cur_w = 0
            for i in range(len_ns):
                if bit[i] == 1:
                    cur_v += nap_second[i][0]
                    cur_w += nap_second[i][1]
            set_second.append((cur_v, cur_w))

        if not set_second:
            set_second.append([0, 0])

        set_first.sort(key=itemgetter(1), reverse=True)
        set_second.sort(key=itemgetter(1))

        res = 0
        for vf, wf in set_first:
            for vs, ws in set_second:
                if wf + ws > l:
                    break
                else:
                    res = max(res, vs + vf)

        print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    dp[1][0] = 0
    for i in range(1, mxw+1):
        if i >= w[1]:
            dp[1][i] = v[1]
        else:
            dp[1][i] = 0

    for u, li  in qs:
        ask_parent(u, li)
        print(dp[u][li])
    return


def ask_parent(id, li):
    par = id // 2
    if id == 1:
        return
    if not li in dp[par]:
        ask_parent(par, li)
    v1 = dp[par][li]
    if w[id]<= li:
        if not li-w[id] in dp[par]:
            ask_parent(par, li-w[id])
        v2 = dp[par][li - w[id]] + v[id]
    else:
        v2 = -1
    dp[id][li] = max(v1, v2)




n = RN()
v = [-1] * (n+1)
w = [-1] * (n+1)
for i in range(n):
    v[i+1], w[i+1] = RA()
q = RN()
qs = [RA() for _ in range(q)]
dp = [{} for _ in range(n+1)]
mxw = max([qw[1] for qw in qs])
solve()

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
W=[]
V=[]
for _ in range(N):
  V_,W_=map(int,input().split())
  W.append(W_)
  V.append(V_)
Q=int(int(input()))
for _ in range(Q):
  v,L=map(int,input().split())
  ls=[]
  n=int(math.log(v,2))+1
  for i in range(n):
    ls.append(v)
    v=v//2
  Ws=[]
  Vs=[]
  for i in range(n):
    Ws.append(W[ls[i]-1])
    Vs.append(V[ls[i]-1])
    
  dp=[[0]*(L+1) for i in range(n+1)]
  for i in range(n):
    for j in range(L+1):
      dp[i+1][j]=max(dp[i+1][j],dp[i][j])
      if j+Ws[i]<=L:
        dp[i+1][j+Ws[i]]=max(dp[i+1][j+Ws[i]],dp[i][j]+Vs[i])
  print(dp[n][L])

Submission status: Time Limit Exceeded

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

N = int(input())
V, W = [-1], [-1]

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

Q = int(input())

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

    VQ, WQ = [], []
    while v > 0:
        VQ.append(V[v])
        WQ.append(W[v])

        v = v // 2

    n = len(VQ)
    n2 = n // 2

    wv = []

    for j in range(1 << n2):
        sv, sw = 0, 0
        for k in range(n2):
            if (j >> k) & 1:
                sv += VQ[k]
                sw += WQ[k]
        wv.append((sw, sv))

    wv.sort()

    m = 1
    for j in range(1, 1 << n2):
        if wv[m-1][1] < wv[j][1]:
            wv[m] = wv[j]
            m += 1

    ans = 0
    for j in range(1 << (n - n2)):
        sv, sw = 0, 0
        for k in range(n - n2):
            if (j >> k) & 1:
                sv += VQ[n2 + k]
                sw += WQ[n2 + k]

        if sw <= L:
            index = bisect.bisect_left(wv[:m], (L-sw, 10**6))
            v2 = wv[index-1][1]
            ans = max(ans, sv + v2)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
L=10**5
item=[(0,0)]
for i in range(n):
    v,w=map(int,input().split())
    item.append((v,w))

dp=[[0 for _ in range(L+1)] for _ in range(n+1)] 

for k in range(item[1][1],L+1):
    dp[1][k]=item[1][0]
    
for i in range(2,n+1):
    for l in range(L+1):
        bi=i//2
        if item[i][1]<=l:
            dp[i][l]=max(dp[bi][l-item[i][1]]+item[i][0],dp[bi][l])
        else:
            dp[i][l]=dp[bi][l]

Q=int(input())
for q in range(Q):
    u,l=map(int,input().split())
    print(dp[u][l])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
VW = [list(map(int,input().split( ))) for _ in range(N)]
Q = int(input())
vL = [list(map(int,input().split( ))) for _ in range(Q)]
for vLi in vL:
    vi = vLi[0]
    Li = vLi[1] 
    vw = VW[vi-1]
    stock = [(vw[0],vw[1])]
    while vi != 1:
        vi = vi//2
        vw = VW[vi-1]
        stock.append((vw[0],vw[1]))
    V = [0 for _ in range(Li+1)]
    for vi,wi in stock[:-1]:
        for l in range(1,Li+1)[::-1]:
            if l >= wi:
                V[l] = max(V[l],V[l-wi] + vi)
            else:
                V[l] = V[l]
    vi = stock[-1][0]
    wi = stock[-1][1]
    if Li >= wi:
    	print(max(V[Li],V[Li-wi] + vi))
    else:
      	print(V[Li])

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    V = [(next(it), next(it)) for i in range(N)]
    Q = next(it)

    bi = N.bit_length()
    B = [1<<i for i in range(bi)]

    x = 1
    for vi, li in zip(it, it):
        aa = []
        ans = 0
        while vi:
            if V[vi-1][1] <= li:
                aa.append(V[vi-1])
            vi >>= 1

        bi = len(aa).bit_length()
        for i in range(1, 1<<len(aa)):
            wi = vi = 0
            for j, jj in zip(range(bi+1), B):
                if i & jj:
                    wi += aa[j][1]
                    if wi > li:
                        break
                    vi += aa[j][0]
            else:
                ans = max(ans, vi)
        print(ans)


if __name__ == "__main__":
    resolve()

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)]
#from collections import defaultdict
dp={}#defaultdict(lambda:-1)
#dp=[[-1]*(10**5+1) for _ in range(n+1)]
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 (i,l) in dp and 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:
import sys
input = sys.stdin.buffer.readline

n = int(input())

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

a = [[] for i in range(2**10)]

for i in range(1,min(n+1,2**10)):
    if i == 1:
        a[i].append((w[1],v[1]))
    else:
        p = i//2
        tank = set([(w[i],v[i])])
        for ww,vv in a[p]:
            tank.add((ww,vv))
            if ww + w[i] <= 10**5:
                tank.add((ww+w[i],vv+v[i]))
        tank = list(tank)
        tank.sort()
        ma = -1
        for j in range(len(tank)):
            ww,vv = tank[j]
            if vv > ma:
                if j == len(tank)-1 or tank[j+1][0] != ww:
                    ma = vv
                    a[i].append((ww,vv))



Q = int(input())
for _ in range(Q):
    now,L = map(int,input().split())
    if now < 2**10:
        if a[now][0][0] > L:
            print(0)
        else:
            ok = 0
            ng = len(a[now])

            while ng - ok > 1:
                mid = (ok+ng)//2
                if a[now][mid][0] > L:
                    ng = mid
                else:
                    ok = mid
            print(a[now][ok][1])
    else:
        pp = [(0,0)]
        while now >= 2**10:
            tank = []
            for ww,vv in pp:
                if ww+w[now] <= L:
                    tank.append((ww+w[now],vv+v[now]))
            for e in tank:
                pp.append(e)
            now = now//2
        
        res = 0

        for ww,vv in pp:
            L -= ww
            if a[now][0][0] > L:
                res = max(res,vv)
            else:
                ok = 0
                ng = len(a[now])

                while ng - ok > 1:
                    mid = (ok+ng)//2
                    if a[now][mid][0] > L:
                        ng = mid
                    else:
                        ok = mid
                res = max(res,a[now][ok][1] + vv)

            L += ww
        print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]
until = min(n, 2**9-1)
# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        ll = l + list((ww+W[v], vv+V[v]) for ww,vv in l)
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
                
        d[v] = tmp
        q.appendleft(v)

from bisect import bisect_right as br
def sub(vv, L):
    if d[vv] is None:
        tmp = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll = tmp + list((wt+W[vv], vt+V[vv]) for wt,vt in tmp)
            ll.sort()
            tmp = [ll[0]]
            for item in ll:
                if tmp[-1][1]<item[1]:
                    tmp.append(item)
            ll = tmp
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = -1
    for w1,v1 in tmp:
        if w1>L:
            continue
        out = br(l, (L-w1, float("inf")))
        ans = max(ans, l[out-1][1]+v1)
    return ans
        
q = int(input())
ans = [None]*q
for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    ans[i] = sub(vv, ll)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
L = 10 ** 5 + 1

N = int(input())

items = []
for _ in range(N):
	v, w = map(int, input().split())
	items.append((v, w))

Q = int(input())
queries = []

for _ in range(Q):
	i, l = map(int, input().split())
	table = { 0: 0 }
	while i > 0:
		new_table = dict(table)
		v, w = items[i - 1]
		for w_min, v_sum in table.items():
			v_sum += v
			w_min += w
			if w_min <= l and (w_min not in table or new_table[w_min] < v_sum):
				new_table[w_min] = v_sum
		i //= 2
		table = new_table
#		print(table)
	print(max(table.values()))

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:
            targets = bin(data)[3:]
            pn = n
            cn = n
            for i, s in enumerate(targets):
                if s == '0':
                    pn = cn
                    cn = cn.left
                else:
                    pn = cn
                    cn = cn.right
            if s == '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 = bin(li[0])[3:]
  cn = tree.root
  items = [[cn.value, cn.weight]]
  for i, s in enumerate(targets):
    if s == '0':
      cn = cn.left
    else:
      cn = cn.right
    items.append([cn.value, cn.weight])
  print(knapsack(0, li[1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 10
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))

  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = len(knapls[anc])
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
                    if k + w0 <= 10 ** 5:
                        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:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    vw=[tuple(map(int,input().split())) for i in range(N)]
    vw=[(0,0)]+vw
    W=10**5
    dp=[[0]*(W+1) for i in range(N+1)]
    for i in range(1,W+1):
        if i < vw[1][1]:
            dp[1][i]=0
        else:
            dp[1][i]=vw[1][0]
    for i in range(2,N+1):
        for w in range(W+1):
            p=int(i//2)
            dp[i][w]=dp[p][w]
            if w>=vw[i][1]:
                dp[i][w]=max(dp[i][w], dp[p][w-vw[i][1]]+vw[i][0])
    Q=int(input())
    for i in range(Q):
        v,L=map(int,input().split())
        print(dp[v][L])    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
L=10**5
item=[(0,0)]
for i in range(n):
    v,w=map(int,input().split())
    item.append((v,w))

dp=[[0 for _ in range(L+1)] for _ in range(n+1)] 

for k in range(item[1][1],L+1):
    dp[1][k]=item[1][0]
    
for i in range(2,n+1):
    for l in range(L+1):
        bi=i//2
        if item[i][1]<=l:
            dp[i][l]=max(dp[bi][l-item[i][1]]+item[i][0],dp[bi][l])
        else:
            dp[i][l]=dp[bi][l]

Q=int(input())
for q in range(Q):
    u,l=map(int,input().split())
    print(dp[u][l])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
V=[]
W=[]
for i in range(N):
    inputs = input().split()
    V.append(int(inputs[0]))
    W.append(int(inputs[1]))
Q=int(input())
v=[]
L=[]
for i in range(Q):
    inputs = input().split()
    v.append(int(inputs[0]))
    L.append(int(inputs[1]))
for i in range(Q):
    l= L[i]
    
    values =[]
    weights=[]
    j=v[i]
    while j >= 1:
     
        values.append(V[j-1])
        weights.append(W[j-1])
        j = int(j/2)
    numbers = len(values)
    dp = [[0]*(l+1) for i in range(numbers+1)]
 
    for item in range(numbers+1):
       
        for wgt in range(l+1):
           
            if item == 0:
                dp[item][wgt]=0
            else:
                if wgt == 0:
                    dp[item][wgt]=0
                else:
                    dp[item][wgt]=dp[item-1][wgt]
            if item>0 and wgt>=weights[item-1]:
                dp[item][wgt]=max(dp[item-1][wgt],dp[item-1][wgt-weights[item-1]]+values[item-1])
                
    
    value = dp[numbers][l]
    print(value)

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)]
from collections import defaultdict
dp=defaultdict(lambda:-1)
#dp=[[-1]*(10**5+1) for _ in range(n+1)]
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:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

import sys
from functools import lru_cache

V = [0]
W = [0]

@lru_cache(maxsize=None)
def solve(v, L):
    if v == 1:
        if W[v] > L:
            return 0
        return V[v]
    p = v // 2

    res = [solve(p, L)]  # not taking v
    if L >= W[v]:
        res.append(solve(p, L - W[v]) + V[v])  # taking v
    return max(res)


def main():
    global V, W
    n = ri()
    for _ in range(n):
        vx, wx = ria()
        V.append(vx)
        W.append(wx)
    q = ri()
    for _ in range(q):
        v, L = ria()
        wi(solve(v, L))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
VW = []
for _ in range(N):
  VW.append(list(map(int,input().split())))
Q = int(input())



def select_or(weight,n, L):
  if n == 1:
    if weight + VW[0][1] <= L:
      return VW[0][0]
    else:
      return 0
  else:
    if weight + VW[n-1][1] <= L:
      return max(VW[n-1][0] + select_or(weight + VW[n-1][1],n//2,L), select_or(weight,n//2,L))
    else:
      return select_or(weight,n//2,L)
    
  

for _ in range(Q):
  v,l = list(map(int,input().split())) 
  ans = select_or(0,v,l)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
V=[0]*n
W=[0]*n
for i in range(n):
  V[i],W[i]=map(int,input().split())
q=int(input())
for _ in range(q):
  v,w=map(int,input().split())
  VV=[]
  WW=[]
  nn=0
  while v>=1:
    VV.append(V[v-1])
    WW.append(W[v-1])
    v=v//2
    nn=nn+1
  V1=VV[0:nn//2]
  V2=VV[nn//2:nn]
  W1=WW[0:nn//2]
  W2=WW[nn//2:nn]
  VW1=[]
  VW2=[]
  for i in range(2**len(V1)):
    s=format(i,"12b")
    A=[]
    for j in range(len(V1)):
      if s[-1-j]=="1":
        A.append(j)
    s=0
    t=0
    for j in range(len(A)):
      s=s+V1[A[j]]
      t=t+W1[A[j]]
    VW1.append([s,t])
  VW1.sort(reverse=True)
  VW11=[]
  s=10**12
  t=10**12
  for i in range(2**len(V1)):
    if VW1[i][0]<s and VW1[i][1]<t:
      VW11.append([VW1[i][0],VW1[i][1]])
      s=VW1[i][0]
      t=VW1[i][1]
  
  
  for i in range(2**len(V2)):
    s=format(i,"12b")
    A=[]
    for j in range(len(V2)):
      if s[-1-j]=="1":
        A.append(j)
    s=0
    t=0
    for j in range(len(A)):
      s=s+V2[A[j]]
      t=t+W2[A[j]]
    VW2.append([s,t])
  VW2.sort(reverse=True)
  V22=[]
  W22=[]
  s=10**12
  t=10**12
  for i in range(2**len(V2)):
    if VW2[i][0]<s and VW2[i][1]<t:
      V22.append(VW2[i][0])
      W22.append(VW2[i][1])
      s=VW2[i][0]
      t=VW2[i][1]
  V22=V22[::-1]
  W22=W22[::-1]
  ans=0
  for i in range(len(VW11)):
    j=bisect.bisect_right(W22,w-VW11[i][1],lo=0, hi=len(W22))
    if j==0:
      continue
    a=VW11[i][0]+V22[j-1]
    if a>ans:
      ans=a
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 11
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))

  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = len(knapls[anc])
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)