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:

n = int(raw_input())
h = {}
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):
	bag = []
	while(v):
		bag.append(h[v])
		v = v/2
	dp = {0:0}

	for i in range(len(bag)):
		for ww in range(l+1)[::-1]:
			cv, cw = bag[i]
			if ww - cw >=0:
				dp[ww] = max(dp[ww] if ww in dp else 0, (dp[ww - cw] if (ww - cw) in dp else 0) + cv)
	
	return dp[l] if l in dp else 0
for _ in range(nq):
	v,l = map(int, raw_input().split(' '))
	print f(v,l,h)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from bisect import bisect_left
 
# from https://atcoder.jp/contests/abc032/submissions/3020872
def solve(N, W, DD):
    L = DD[:N // 2]
    M = DD[N // 2:]
    s = len(L)
    t = len(M)
    A = set()
    B = []
    for i in range(1 << s):
        v, w = 0, 0
        for j in range(s):
            if i & (1 << j):
                v += L[j][0]
                w += L[j][1]
        if w <= W:
            A.add((w, v))
    for i in range(1 << t):
        v, w = 0, 0
        for j in range(t):
            if i & (1 << j):
                v += M[j][0]
                w += M[j][1]
        if w <= W:
            B.append((w, v))
    B = sorted(B, key=itemgetter(1, 0))
    value = 0
    maxv = [0]
    for w,v in B:
        maxv.append(max(maxv[-1],v))
    for w, v in A:
        x = bisect_left(B, (W - w + 1, 0))
        if x==0:
            continue
        if maxv[x] + v > value:
            value = maxv[x] + v
    return value
        
def main():
    input = sys.stdin.readline
    N = int(input())
    VW = [0] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        vw = []
        while V > 0:
            vw.append(VW[V])
            V //= 2
        ans = solve(N, L, vw)
        Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    N = int(readline())
    VW = [list(map(int, readline().split())) for i in range(N)]
    Q = int(readline())
    vL = [list(map(int, readline().split())) for i in range(Q)]

    mem = {}

    for v, L in vL:
        print(rec(v-1, L, VW, mem))

def rec(n, cap, VW, mem):
    p = (n, cap)
    if p in mem:
        return mem[p]
    
    v, w = VW[n]
    if n == 0:
        if cap >= w:
            return v
        else:
            return 0

    parent = (n - 1) // 2
    if cap < w:
        ret = rec(parent, cap, VW, mem)
    else:
        ret = max(
            rec(parent, cap, VW, mem),
            rec(parent, cap - w, VW, mem) + v
        )
    
    mem[p] = ret
    return ret

solve()

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N=int(input())
VW=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
Q=int(input())

def solve(MAX):
    #print(X)
    LEN=len(X)

    T={0:0}

    for v,w in X[:LEN//2]:

        T0=dict(T)
        for k,val in T.items():
            if k+w>MAX:
                continue
            if k+w in T0:
                T0[k+w]=max(T0[k+w],val+v)
            else:
                T0[k+w]=val+v
        T=T0

    R=[]
    v=0
    for k in sorted(T):
        v=max(v,T[k])
        R.append((k,v))
        

    T={0:0}

    for v,w in X[LEN//2:]:

        T1=dict(T)
        for k,val in T.items():
            if k+w>MAX:
                continue
            if k+w in T1:
                T1[k+w]=max(T1[k+w],val+v)
            else:
                T1[k+w]=val+v
        T=T1

    L=[]
    v=0
    for k in sorted(T):
        v=max(v,T[k])
        L.append((k,v))

    ANS=0
    ind=len(L)-1

    #print(R,L)

    for k0,v0 in R:
        while ind>0 and L[ind][0]+k0>MAX:
            ind-=1
        if ind>=0:
            ANS=max(ANS,L[ind][1]+v0)
        else:
            break

    print(ANS)


for tests in range(Q):
    v,L=map(int,input().split())
    X=[]
    while v!=0:
        X.append(VW[v])
        v//=2
    solve(L)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
VW = tuple(tuple(map(int, input().split())) for _ in range(N))
q = int(input())
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つの全列挙を元に解を求める
    res = max(solve(T0, T1))
    return res

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

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**10-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, ll):
    while d[vv] is None:
        vv = (vv-1)//2
    l = d[vv]
    out = br(l, (ll, float("inf")))
    return l[out-1][1]
        
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:
import sys
input = sys.stdin.readline

N = int(input())
V = []
W = []
for n in range(N):
  V_, W_ = map(int, input().split())
  V.append(V_)
  W.append(W_)
Q = int(input())

def query(v, L):
  vlist = []
  while v > 0:
    vlist.append(v)
    v = v // 2
  dp = [[0] * (L+1) for l in range(len(vlist) + 1)]
  for k in range(len(vlist)):
    for l in range(L+1):
      if l < W[vlist[k]-1]:
        dp[k+1][l] = dp[k][l]
      else:
        dp[k+1][l] = max(dp[k][l], dp[k][l-W[vlist[k]-1]] + V[vlist[k]-1])
  print(dp[len(vlist)][L])


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

Submission status: Time Limit Exceeded

Solution code:
import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
mp = iter(inp[n * 2 + 1:])
queries = []
required = [-1] * (n + 1)
for q in zip(mp, mp):
    queries.append(q)
    v, l = q
    while v > 0:
        if required[v] >= l:
            break
        required[v] = l
        v >>= 1

cache = [None] * (n + 1)
cache[0] = {0: 0}
for u in range(1, n + 1):
    r = required[u]
    if r == -1:
        continue
    par = cache[u >> 1]
    dp = par.copy()
    v = vvv[u]
    w = www[u]
    for cw, cv in par.items():
        nw = cw + w
        if nw > r:
            continue
        nv = cv + v
        if nw not in dp or dp[nw] < nv:
            dp[nw] = nv
    cache[u] = dp

buf = []
for u, l in queries:
    buf.append(max((v for w, v in cache[u].items() if w <= l), default=0))
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[:],i4[:],i4)', cache=True)
def solve(values, weights, lim):
    N = len(values)
    if N == 1:
        if weights[0] <= lim:
            return values[0]
        else:
            return 0

    def compute_half(values, weights, lim):
        N = len(values)
        V = np.empty(1 << N, np.int32)
        W = np.empty(1 << N, np.int32)
        V[0], W[0] = 0, 0
        for i in range(N):
            for j in range(1 << i):
                V[j + (1 << i)] = V[j] + values[i]
                W[j + (1 << i)] = W[j] + weights[i]
        ind = W.argsort()
        V = V[ind]
        W = W[ind]
        for i in range(1, 1 << N):
            V[i] = max(V[i - 1], V[i])
        ind1 = W <= lim
        V = V[ind1]
        W = W[ind1]
        return V, W

    n = N // 2
    VL, WL = compute_half(values[:n], weights[:n], lim)
    VR, WR = compute_half(values[n:], weights[n:], lim)
    best = 0
    j = len(WR) - 1
    for i in range(len(WL)):
        while WL[i] + WR[j] > lim:
            j -= 1
        x = VL[i] + VR[j]
        best = max(best, x)
    return best

@njit('(i4,i4[:],i4[:],i4[:],i4[:])', cache=True)
def main(N, V, W, v, L):
    Q = len(v)
    values = np.empty(18, np.int32)
    weights = np.empty(18, np.int32)
    for i in range(Q):
        n = v[i]
        p = 0
        while n:
            values[p] = V[n]
            weights[p] = W[n]
            p += 1
            n >>= 1
        x = solve(values[:p], weights[:p], L[i])
        print(x)

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2], query[1::2]

main(N, V, W, v, L)

Submission status: Time Limit Exceeded

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

d = dict()


def rec(i, j):
    if i == 1:
        return X[0][0] if j >= X[0][1] else 0
    if (i, j) in d:
        return d[(i, j)]

    ret = rec(i // 2, j)
    if j >= X[i - 1][1]:
        ret = max(ret, rec(i // 2, j - X[i - 1][1]) + X[i - 1][0])
    d[(i, j)] = ret
    return ret


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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
vw=[[0,0]]+[list(map(int,input().split())) for i in range(n)]
q=int(input())


def aaa(x,w,l):
  n=len(x)
  if n==1:
    if w[0]<=l:
      return x[0]
    else:
      return 0
  elif w[0]<=l:
    return max(aaa(x[1:],w[1:],l),x[0]+aaa(x[1:],w[1:],l-w[0]))
  else:
    return aaa(x[1:],w[1:],l)


for dummy in range(q):
  a,l=map(int,input().split())
  x=[]
  y=[]
  while a>=1:
    x.append(vw[a][0])
    y.append(vw[a][1])
    a//=2
  print(aaa(x,y,l))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

for p, l in PL:
    pp = p
    dp = [0 for i in range(l + 1)]
    index = 0
    while pp:
        v, w = VW[pp - 1]
        for j in range(l, -1, -1):
            if dp[j] and j + w <= l:
                dp[j + w] = max(dp[j + w], dp[j] + v)
        if w <= l: dp[w] = max(dp[w], dp[0] + v)
        pp >>= 1
        index += 1
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n = int(input())
tree = []
for i in range(n):
    v, w = map(int, input().split())
    tree.append((v, w))


@lru_cache(None)
def f(node, val, lim):
    if node == 0:
        return val + tree[0][0] if tree[0][1] <= lim else val
    else:
        p = (node - 1) // 2
        res = f(p, val, lim)
        if lim >= tree[node][1]:
            res = max(res, f(p, val + tree[node][0], lim - tree[node][1]))
        return res


for _ in range(int(input())):
    node, lim = map(int, input().split())
    print(f(node - 1, 0, lim))

Submission status: Time Limit Exceeded

Solution code:
def solve(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())
v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, input().split())
q = int(input())
for i in range(q):
    va, l = map(int, input().split())
    a = []
    b = []
    t = 0
    while va > 0:
        t += 1
        a.append(v[va - 1])
        b.append(w[va - 1])
        va >>= 1
    print(solve(t, l, b, a))

Submission status: Time Limit Exceeded

Solution code:
def knapsack_meetinthemiddle(n, cap, item):
    if n % 2 != 0: item.append((0, 0))
    m = (n + 1) // 2
    M = 2**m
    item1 = item[:m]
    item2 = item[m:]
    S1 = [None] * (M)
    S2 = [None] * (M)
    for i in range(M):
        sumv1, sumw1, sumv2, sumw2 = 0, 0, 0, 0
        for j in range(m):
            if (i >> j) & 1:
                v1, w1 = item1[j]
                v2, w2 = item2[j]
                sumv1 += v1
                sumw1 += w1
                sumv2 += v2
                sumw2 += w2
        S1[i] = (sumw1, sumv1)
        S2[i] = (sumw2, sumv2)
    S1.sort()
    S2.sort()
    res, j, tmp = 0, 0, 0
    for sw1, sv1 in S1[::-1]:
        if sw1 > cap: continue
        while j < M and sw1 + S2[j][0] <= cap:
            tmp = max(tmp, S2[j][1])
            j += 1
        res = max(res, sv1 + tmp)
    return res

N = int(input())

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

Q = int(input())

for _ in range(Q):
    u, L = map(int, input().split())
    item = []
    cnt = 0
    while u:
        item.append(I[u - 1])
        cnt += 1
        u //= 2
    print(knapsack_meetinthemiddle(cnt, L, item))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from operator import itemgetter

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

	prov, tmp = upperbound(0, 0, -1)
	h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
	while h:
		_v, w, v, cur = heappop(h)
		if _v > prov or cur == N - 1:
			continue
		nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
		if nxtw >= M:
			heappush(h, (_v, nxtw, nxtv, cur + 1))
		_prov, ub = upperbound(w, v, cur)
		if _prov < prov:
			prov = _prov
		if ub < prov:
			heappush(h, (ub, w, v, cur + 1))
	return -prov
"""


def solve(N, W, VW):
	VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
	v_max = 0

	def solve_relax(i, cap):
		ans = 0
		for v, w in VW[i:]:
			if not cap: break
			if w <= cap:
				cap -= w
				ans += v
			else:
				ans += v * (cap / w)
				return ans, False
		return ans, True

	def dfs(i, v_now, w_now):
		nonlocal v_max
		if i == N:
			v_max = max(v_max, v_now)
			return v_now
		relax, relax_ok = solve_relax(i, W - w_now)
		relax += v_now
		if relax_ok:
			v_max = max(v_max, relax)
			return relax
		if relax < v_max:
			return 0
		ans = 0
		v, w = VW[i]
		if w_now + w <= W:
			ans = max(ans, dfs(i + 1, v_now + v, w_now + w))
		ans = max(ans, dfs(i + 1, v_now, w_now))
		return ans

	return dfs(0, 0, 0)

import sys
input = sys.stdin.buffer.readline
n=int(input())
items=[(0,0,0)]
for _ in range(n):
	v,w=map(int,input().split())
	items.append((v,w))
q=int(input())
ans=[]
for _ in range(q):
	v,l=map(int,input().split())
	_items=[items[1]]
	c=1
	while v!=1:
		_items.append(items[v])
		v//=2
		c+=1
	#print(_items)
	ans.append(solve(c,l,_items))
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    VW = [(0,0)]
    for _ in range(N):
        v, w = map(int, readline().split())
        VW.append((v,w))

    Q = int(readline())
    for _ in range(Q):
        v, L = map(int, readline().split())
        dp = [0] * (L+1)
        while v>0:
            V = VW[v][0]
            W = VW[v][1]
            for j in range(L, -1, -1):
                if j - W >= 0:
                    dp[j] = max(dp[j], dp[j - W] + V)
            v//=2
        print(dp[L])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

q = int(input())

#for L in range(1,10**5+1):

for _ in range(q):
    v,l = map(int,input().split())
    node = []
    while v > 1:
        node.append(v)
        v //= 2
    node.append(1)
    dp = [0]*(l+1)
    for i in node:
        dp_past = list(dp)
        v,w = item[i-1]
        for W in range(l+1):
            if W-w >= 0:
                dp[W] = max(dp_past[W],dp_past[W-w]+v)

    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
V=[]
W=[]
S=10**5
D=[[0]*(S+1) for _ in range(N+1)] #D[x][k]:wまで,重さw以下

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

for x in range(1,N+1):
    for w in range(S+1):
        if w>=W[x-1]:
            D[x][w]=max(D[x>>1][w],D[x>>1][w-W[x-1]]+V[x-1])
        else:
            D[x][w]=D[x>>1][w]
            
Q=int(input())
for _ in range(Q):
    v,L=map(int,input().split())
    print(D[v][L])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, VW, Q, VL):
    V = [0] + [v for v, w in VW]
    W = [0] + [w for v, w in VW]

    from collections import Counter
    def f(u, l):
        memo = Counter()
        memo[0] = 0
        while u != 0:
            nm = Counter()
            for w, v in memo.items():
                if w+W[u] <= l:
                    nm[w+W[u]] = max(nm[w+W[u]], v + V[u])
                nm[w] = max(nm[w], v)
            memo = nm
            u //= 2
        return max(memo.values())

    ans = []
    for v, l in VL:
        ans.append(f(v, l))
    return ans


def main():
    N = read_int()
    VW = [read_int_n() for _ in range(N)]
    Q = read_int()
    VL = [read_int_n() for _ in range(Q)]
    print(*slv(N, VW, Q, VL), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(values, weights, n, W):
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

    for i in range(n):
        for j in range(W+1):
            if j < weights[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j-weights[i]] + values[i])

    return max(dp[-1])


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

    values[i+1] = v
    weights[i+1] = w

q = int(input())
for _ in range(q):
    v, L = list(map(int, input().strip().split()))

    val, wgt = [], []

    while v:
        val.append(values[v])
        wgt.append(weights[v])
        v >>= 1

    #print(L, val, wgt)

    print(solve(val, wgt, len(wgt), L))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
napls=[[0,0]]*n
for i in range(n):
  napls[i]=list(map(int,input().split()))
q=int(input())
#ナップザックだから
#dp[n個目][重さ]=価値
ls=[]
for i in range(q):
  v,l=map(int,input().split())
  while True:
    ls.append(napls[v-1])
    if v==1:
      break
    v=v//2
    
  dp=[[0 for j in range(l+1)] for k in range(len(ls))]
  for j in range(len(ls)):
    w=ls[j][1]
    va=ls[j][0]
    for k in range(l+1):
      if k>=w:
        if j==0:
          dp[j][k]=va
        else:
          dp[j][k]=max(dp[j-1][k-w]+va,dp[j-1][k])
      else:
        if j!=0:
          dp[j][k]=dp[j-1][k]
  print(dp[len(ls)-1][l])
  #print(dp)
  ls.clear()

Submission status: Time Limit Exceeded

Solution code:
import sys

# from https://tjkendev.github.io/procon-library/python/dp/knapsack-meet-in-the-middle.html
def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw

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

def main():
    input = sys.stdin.readline
    N = int(input())
    VW = [0] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        vw = []
        while V > 0:
            vw.append(VW[V])
            V //= 2
        ans = solve(len(vw), L, vw)
        Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
n=int(input())

map1=[(0,0)]*n
for i in range(n):
    vn,w=map(int,input().split())
    map1[i]=(vn,w)
    
def main():
    q=int(input())
    for _ in range(q):
        v,l=map(int,input().split())
        length=v.bit_length()
        dd = defaultdict(int)
        dd[0] = 0
        while v:
            for tw, tv in list(dd.items()):
                a,b=map1[v-1]
                if tw + b <= l:
                    dd[tw + b] = max(tv + a, dd[tw + b])
            v//=2
        print(max(dd.values()))
        #print(dd)     

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
import math
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    VW = [(0,0)]
    for _ in range(N):
        v, w = map(int, readline().split())
        VW.append((v,w))

    Q = int(readline())
    for _ in range(Q):
        v, L = map(int, readline().split())
        length = math.floor(math.log2(v)) + 1
        V = []
        W = []
        while v>0:
            V.append(VW[v][0])
            W.append(VW[v][1])
            v//=2
        dp = [0] * (L+1)
        for i in range(length):
            v = V[i]
            w = W[i]
            for j in range(L,-1,-1):
                if j-w>=0:
                    dp[j] = max(dp[j], dp[j-w]+v)
        print(dp[L])




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[:],i4[:],i4)', cache=True)
def solve(values, weights, lim):
    N = len(values)
    if N == 1:
        if weights[0] <= lim:
            return values[0]
        else:
            return 0

    def compute_half(values, weights, lim):
        N = len(values)
        V = np.empty(1 << N, np.int32)
        W = np.empty(1 << N, np.int32)
        V[0], W[0] = 0, 0
        for i in range(N):
            V[1 << i:1 << (i + 1)] = V[:1 << i] + values[i]
            W[1 << i:1 << (i + 1)] = W[:1 << i] + weights[i]
        ind = W.argsort()
        V = V[ind]
        W = W[ind]
        for i in range(1, 1 << N):
            V[i] = max(V[i - 1], V[i])
        ind1 = W <= lim
        V = V[ind1]
        W = W[ind1]
        return V, W

    n = N // 2
    VL, WL = compute_half(values[:n], weights[:n], lim)
    VR, WR = compute_half(values[n:], weights[n:], lim)
    best = 0
    j = len(WR) - 1
    for i in range(len(WL)):
        while WL[i] + WR[j] > lim:
            j -= 1
        x = VL[i] + VR[j]
        best = max(best, x)
    return best

@njit('(i4,i4[:],i4[:],i4[:],i4[:])', cache=True)
def main(N, V, W, v, L):
    Q = len(v)
    for i in range(Q):
        n = v[i]
        values = np.empty(18, np.int32)
        weights = np.empty(18, np.int32)
        p = 0
        while n:
            values[p] = V[n]
            weights[p] = W[n]
            p += 1
            n >>= 1
        x = solve(values[:p], weights[:p], L[i])
        print(x)

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2], query[1::2]

main(N, V, W, v, L)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from operator import itemgetter


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

	prov, tmp = upperbound(0, 0, -1)
	h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
	while h:
		_v, w, v, cur = heappop(h)
		if _v > prov or cur == N - 1:
			continue
		nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
		if nxtw >= M:
			heappush(h, (_v, nxtw, nxtv, cur + 1))
		_prov, ub = upperbound(w, v, cur)
		if _prov < prov:
			prov = _prov
		if ub < prov:
			heappush(h, (ub, w, v, cur + 1))
	return -prov

import sys
input = sys.stdin.buffer.readline
n=int(input())
items=[(0,0,0)]
for _ in range(n):
	v,w=map(int,input().split())
	items.append((-v,-w,v/w))
q=int(input())
ans=[]
for _ in range(q):
	v,l=map(int,input().split())
	_items=[items[1]]
	c=1
	while v!=1:
		_items.append(items[v])
		v//=2
		c+=1
	_items.sort(key=itemgetter(2),reverse=True)
	#print(_items)
	ans.append(branchAndBound(c,-l,_items))
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

for p, l in PL:
    pp = p
    dp = [[0 for i in range(l + 1)] for j in range(19)]
    index = 0
    while pp:
        v, w = VW[pp - 1]
        for j in range(l + 1):
            if j + w <= l:
                dp[index][j + w] = max(dp[index][j + w], dp[index - 1][j] + v)
            dp[index][j] = max(dp[index][j], dp[index - 1][j])
            #print(index, j + w, l)
        pp >>= 1
        index += 1
    print(max(dp[index - 1]))