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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
from bisect import bisect_left

n = int(readline())
g = []
for i in range(n):
  v,W = map(int,readline().split())
  g.append((v,W))
  
q = int(readline())
for i in range(q):
  V,W = map(int,readline().split())
  DD = []
  ans = 0
  while V > 0:
    DD.append(g[V-1])
    V //= 2
  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))
  B = sorted(B, key=itemgetter(0))
  value = 0
  maxv = [0]
  for w,v in B:
      maxv.append(max(maxv[-1],v))
  #print(A)
  #print(B)
  for w, v in A:
      x = bisect_left(B, (W - w + 1, 0))
      if x==0:
          continue
      value = max(value, maxv[x]+ v)
  print(value)

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**9+1000)]

for i in range(1,min(n+1,2**9+1000)):
    if i == 1:
        a[i].append((w[1],v[1]))
    else:
        p = i//2
        tank = [(w[i],v[i])]
        for ww,vv in a[p]:
            tank.append((ww,vv))
            if ww + w[i] <= 10**5:
                tank.append((ww+w[i],vv+v[i]))
        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**9+1000:
        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**9+1000:
            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:
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

Q = int(input())
for _ in range(Q):
    v,l = map(int, input().split())
    temp = [(L[0][0], L[0][1])]
    while v > 1:
        temp.append((L[v-1][0], L[v-1][1]))
        v //= 2
    M = len(temp)
    ans = 0
    for i in range(2**M):
        cnt = 0
        w = 0
        for j in range(M):
            if i & (1<<j):
                cnt += temp[j][0]
                w += temp[j][1]
        if w <= l:
            ans = max(ans, cnt)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    half = min(2 ** 9, N)

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

    MAX_W = 10 ** 5 + 1

    dp = [[0] * (MAX_W) for _ in range(half + 1)]

    for i in range(1, half + 1):
        V, W = VW[i - 1][0], VW[i - 1][1]
        for j in range(W):
            dp[i][j] = dp[i // 2][j]
        for j in range(W, MAX_W):
            dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)


    def calc(n, L):
        ans = 0
        lst = []
        lst_append = lst.append
        while n > half:
            lst_append(n)
            n //= 2
        # print (lst)
        length = len(lst)
        for i in range(2 ** length):
            v = 0
            w = 0
            for j in range(length):
                if ((i >> j) & 1):
                    v += VW[lst[j] - 1][0]
                    w += VW[lst[j] - 1][1]
            if L >= w:
                ans = max(ans, dp[n][L - w] + v) 
        return ans

    Q = int(input())
    for _ in range(Q):
        v, L = map(int, input().split())
        if v > half:
            print (calc(v, L))
        else: #こっち側はOK(当然)
            print (dp[v][L])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba

#@numba.njit("i8(i8,i8,i8[:,:])")

@numba.njit("i8[:,:](i8[:,:],i8)", cache=True)
def make(S, W):
    T = {0: 0}
    for i in range(len(S)):
        v = S[i][0]
        w = S[i][1]
        # 価値v, 重さw
        T0 = T.copy()
        T_list = list(T.items())
        for j in range(len(T)):
            k = T_list[j][0]
            val = T_list[j][1]
            if k+w > W:
                continue
            if k+w in T0:
                if val+v > T0[k+w]:
                    T0[k+w] = val + v
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = [(0,0)]*0
    T = np.array(list(T.items()), dtype=np.int64)
    T = T[np.argsort(T[:, 0])]
    for i in range(len(T)):
        k = T[i][0]
        Tk = T[i][1]
        if Tk > v:
            v = Tk
        # (重さk, 重さk以下での価値の最大v)
        R.append((k, v))
    return np.array(R, dtype=np.int64)

def solve(N, W, S):
    # S[i] = (v, w): 価値v, 重さw
    
    if N==1:
        return S[0][0] if S[0][1] <= W else 0

    def solve(T0, T1):
        T0 = T0[np.argsort(T0[:, 0])]
        T1 = T1[np.argsort(T1[:, 0])]
        T1 = T1[::-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(np.array(S[:N//2], dtype=np.int64), W)
    T1 = make(np.array(S[N//2:], dtype=np.int64), W)

    # 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(int(ans))
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
vws = []
for _ in range(n):
    v, w = map(int, input().split())
    vws.append((v, w))
q = int(input())
querys = []
for _ in range(q):
    v, l = map(int, input().split())
    querys.append((v, l))
def solve(vw, dp=None, l=10**5):
    if dp is None:
        dp = {0: 0}
    for va, we in vw:
        newdp = dp.copy()
        for w in dp:
            if w+we>l:
                continue
            if w+we in newdp.keys():
                if newdp[w+we]<dp[w]+va:
                    newdp[w+we] = dp[w]+va
            else:
                newdp[w+we] = dp[w]+va
        dp = newdp
    return dp
dps = []
PRE = min(64, n)
for ver in range(1, PRE+1):
    vw = []
    while ver>0:
        vw.append(vws[ver-1])
        ver//=2
    dps.append(solve(vw))
    
for ver, l in querys:
    if ver<=PRE:
        dp = dps[ver-1]
    else:
        vw = []
        while ver>PRE:
            vw.append(vws[ver-1])
            ver//=2
        dp = solve(vw, dps[ver-1], l)
    print(max(j for i, j in dp.items() if i<=l))

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)
    lnap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = lnap
      if i and wn >= ls[i-1][1] and vn <= ls[i-1][0]:
        continue
      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:
def main():
    M = 2**10
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)

    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    memo = {}
    def rec(n,l):
        if n < M:
            return dp[n][l]
        elif (n,l) in memo:
            return memo[(n,l)]
        else:
            c = 0
            if l>=W[n-1]:
                c = rec(n//2,l-W[n-1])+V[n-1]
            res = max(rec(n//2,l),c)
            memo[(n,l)] = res
            return res

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

    for i in range(Q):
        v,L = vL[i]
        print(rec(v,L))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
V = [0] * N
W = [0] * N
for n in range(N):
  V[n], W[n] = [int(x) for x in input().split(' ')]
Q = int(input())
X = [0] * Q
L = [0] * Q
for q in range(Q):
  X[q], L[q] = [int(x) for x in input().split(' ')]

  
DP = [None] * N  # max value when weight total is equal or less than index
M = 10 ** 5 + 5
def dp(x):
  if DP[x] is not None:
    return DP[x]
  if x == 0:
    prev = [(0, 0)]
  else:
    prev = dp((x+1)//2-1)
  # print(x, prev)
  tmp = []
  W_todo = True
  for w, v in prev:
    tmp.append((w, v))
    tmp.append((w + W[x], v + V[x]))
  tmp = sorted(tmp, key=lambda p: (p[0], -p[1]))
  DP[x] = []
  current_v = -1
  for w, v in tmp:
    if v > current_v:
      DP[x].append((w, v))
      current_v = v
    if w > 10 ** 5+100:
      break
  return DP[x]

def solve(x, l):
  tmp = dp(x-1)
  current_v = -1
  for w, v in tmp:
    if w <= l:
      current_v = v
  return current_v

for x, l in zip(X, L):
  print(solve(x, l))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from itertools import accumulate
from collections import defaultdict
import bisect
input = sys.stdin.buffer.readline

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

dp_dict = [defaultdict(lambda: 0)]
dp_dict[0][0] = 0
dp_dict[0][vws[0][1]] = vws[0][0]

for i in range(1, min(2**9, N)):
    v, w = vws[i]
    dp_dict.append(dp_dict[(i-1)//2].copy())
    for w_sum, v_sum in dp_dict[(i-1)//2].items():
        dp_dict[i][w_sum + w] = max(v_sum + v, dp_dict[i][w_sum + w])

values_list = []
weights_list = []
for d in dp_dict:
    ls = sorted(d.items(), key = itemgetter(0))
    weights, values = zip(*ls)
    values = list(accumulate(values, max))
    values_list.append(values)
    weights_list.append(weights)
        
Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    if V-1 < len(dp_dict):
        index = bisect.bisect_right(weights_list[V-1], L) - 1
        print(values_list[V-1][index])
    else:
        V -= 1
        d = defaultdict(lambda: 0)
        d[0] = 0
        while V >= len(dp_dict):
            v, w = vws[V]
            iterator = list(d.items())
            for w_sum, v_sum in iterator:
                d[w_sum + w] = max(v_sum + v, d[w_sum + w])
            V = (V-1) // 2

        v_max = 0
        for w1, v1 in d.items():
            index = bisect.bisect_right(weights_list[V], L-w1) - 1
            if index == -1:
                continue
            v_max = max(v_max, v1 + values_list[V][index])
        print(v_max)

Submission status: Time Limit Exceeded

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

MAX = int(1e5)


def get_dp(V, W, node, memo):
    if memo[node-1]:
        return memo[node-1]
    if node == 1:
        memo[node-1] = [(0, 0), (W[0], V[0])]
        return memo[node-1]
    v = V[node-1]
    w = W[node-1]
    par = get_dp(V, W, node//2, memo)
    idx1 = 0
    idx2 = 0
    ret = [None] * len(par) * 2
    maxval = 0
    i = 0
    while idx1 < len(par) or idx2 < len(par):
        if idx1 < len(par) and par[idx1][0] <= par[idx2][0] + w:
            if par[idx1][0] == par[idx2][0] + w and par[idx1][1] < par[idx2][1] + v:
                maxval = max(maxval, par[idx2][1]+v)
                nxt = (par[idx2][0]+w, maxval)
                idx2 += 1
            else:
                maxval = max(maxval, par[idx1][1])
                nxt = (par[idx1][0], maxval)
                idx1 += 1
        else:
            maxval = max(maxval, par[idx2][1]+v)
            nxt = (par[idx2][0]+w, maxval)
            idx2 += 1
        ret[i] = nxt
        i += 1
    return ret


def bin_search(lst, value):
    lo = 0
    hi = len(lst)
    while lo < hi:
        mid = (lo + hi) // 2
        if lst[mid][0] > value:
            hi = mid
        else:
            lo = mid + 1
    return lo


def query(V, W, node, L, memo):
    par = get_dp(V, W, node, memo)
    v = V[node-1]
    w = W[node-1]
    idx = bin_search(par, L) - 1
    return par[idx][1]


def main():
    N = int(input())
    V = [0] * N
    W = [0] * N
    for i in range(N):
        V[i], W[i] = map(int, input().split())
    memo = [None] * N
    Q = int(input())
    for i in range(Q):
        v, L = map(int, input().split())
        ans = query(V, W, v, L, memo)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    M = 2**11
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)

    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    memo = {}
    def rec(n,l):
        if n < M:
            return dp[n][l]
        elif (n,l) in memo:
            return memo[(n,l)]
        else:
            c = 0
            if l>=W[n-1]:
                c = rec(n//2,l-W[n-1])+V[n-1]
            res = max(rec(n//2,l),c)
            memo[(n,l)] = res
            return res

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

    for i in range(Q):
        v,L = vL[i]
        print(rec(v,L))

if __name__ == '__main__':
    main()

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 = [(w[i],v[i])]
        for ww,vv in a[p]:
            tank.append((ww,vv))
            if ww + w[i] <= 10**5:
                tank.append((ww+w[i],vv+v[i]))
        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:

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

Q=int(input())
L=0
for q in range(Q):
    u,l=map(int,input().split())
    que.append((u,l))
    L=max(L,l)

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]
      
for u,l in que:
    print(dp[u][l])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
VW = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (10**5 + 1) for _ in range(N + 1)]
for i, (v, w) in enumerate(VW, 1):
    for l in range(10**5 + 1):
        if l < w: dp[i][l] = dp[i//2][l]
        else: dp[i][l] = max(dp[i//2][l], dp[i//2][l - w] + v)
Q = int(input())
ans = []
for _ in range(Q):
    v, L = map(int, input().split())
    ans.append(dp[v][L])
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

S = [list(map(int, input().split())) for _ in range(n)]
q = int(input())

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

dp = [[-1]*(10**5+10) for _ in range(n+1)]


def knapsack(v, L):
    if v == 1:
        if S[v-1][1] > L:
            dp[v][L] = 0
            return 0
        else:
            dp[v][L] = S[v-1][0]
            return S[v-1][0]
    if dp[v][L] != -1:
        return dp[v][L]
    if L < S[v-1][1]:
        dp[v][L] = knapsack(v//2, L)
    else:
        #print(knapsack(v//2, L))
        #print(knapsack(v//2, L-S[v-1][1])+S[v-1][0])
        dp[v][L] = max(knapsack(v//2, L),
                       knapsack(v//2, L-S[v-1][1])+S[v-1][0])
    return dp[v][L]


for v, L in vl:
    print(knapsack(v, L))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from itertools import accumulate
from collections import defaultdict
import bisect
input = sys.stdin.buffer.readline

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

dp_dict = [defaultdict(lambda: 0)]
dp_dict[0][0] = 0
dp_dict[0][vws[0][1]] = vws[0][0]

for i in range(1, min(2**14, N)):
    v, w = vws[i]
    dp_dict.append(dp_dict[(i-1)//2].copy())
    for w_sum, v_sum in dp_dict[(i-1)//2].items():
        dp_dict[i][w_sum + w] = max(v_sum + v, dp_dict[i][w_sum + w])

values_list = []
weights_list = []
for d in dp_dict:
    ls = sorted(d.items(), key = itemgetter(0))
    weights, values = zip(*ls)
    values = list(accumulate(values, max))
    values_list.append(values)
    weights_list.append(weights)
        
Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    if V-1 < len(dp_dict):
        index = bisect.bisect_right(weights_list[V-1], L) - 1
        print(values_list[V-1][index])
    else:
        V -= 1
        d = defaultdict(lambda: 0)
        d[0] = 0
        while V >= len(dp_dict):
            v, w = vws[V]
            iterator = list(d.items())
            for w_sum, v_sum in iterator:
                d[w_sum + w] = max(v_sum + v, d[w_sum + w])
            V = (V-1) // 2

        v_max = 0
        for w1, v1 in d.items():
            index = bisect.bisect_right(weights_list[V], L-w1) - 1
            if index == -1:
                continue
            v_max = max(v_max, v1 + values_list[V][index])
        print(v_max)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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


@lru_cache(maxsize=10 ** 18)
def dp(v, l):
    if v == 0:
        return 0
    parent = v // 2
    V, W = VW[v - 1]
    if l - W < 0:
        return dp(parent, l)

    return max(dp(parent, l - W) + V, dp(parent, l))


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

pass

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**8-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:
        ll = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll.extend(list((wt+W[vv], vt+V[vv]) for wt,vt in ll))
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
        tmp = ll
    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:
def main():
    M = 2**12
    N = int(input())
    V = []
    W = []
    for i in range(N):
        v,w = map(int,input().split())
        V.append(v)
        W.append(w)

    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)

    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    memo = {}
    def rec(n,l):
        if n < M:
            return dp[n][l]
        elif (n,l) in memo:
            return memo[(n,l)]
        else:
            c = 0
            if l>=W[n-1]:
                c = rec(n//2,l-W[n-1])+V[n-1]
            res = max(rec(n//2,l),c)
            memo[(n,l)] = res
            return res

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

    for i in range(Q):
        v,L = vL[i]
        print(rec(v,L))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
import numpy as np


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:
                    j = li[cnt]
                    v, w = V[j - 1], W[j - 1]
                    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(readline())
    Z = np.array(read().split(), np.int64)
    V = Z[0:2 * n:2]
    W = Z[1:2 * n:2]
    U = Z[2 * n + 1::2]
    L = Z[2 * n + 2::2]

    for u, l in zip(U, L):
        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)

        W2 = np.array(list(d2.keys()), np.int64)
        V2 = np.array(list(d2.values()), np.int64)
        idx = np.argsort(W2)
        W2 = W2[idx]
        V2 = V2[idx]
        V2 = np.maximum.accumulate(V2)

        K1 = np.array(list(d1.keys()), np.int64)
        V1 = np.array(list(d1.values()), np.int64)
        IDX = np.searchsorted(W2, l - K1, "right") - 1
        VAL = V1 + V2[IDX]
        ans = VAL.max()
        print(ans)


if __name__ == "__main__":
    main()

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] 
    V = [0 for _ in range(Li+1)]
    while vi != 1:
        vw = VW[vi-1]
        Vi = vw[0]
        Wi = vw[1]
        for l in range(1,Li+1)[::-1]:
            if l >= Wi:
                V[l] = max(V[l],V[l-Wi] + Vi)
        vi = vi//2
    vw = VW[0]
    Vi = vw[0]
    Wi = vw[1]
    if Li >= Wi:
        print(max(V[Li],V[Li-Wi] + Vi))
    else:
        print(V[Li])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
# i番目の重みws[i], 価値vs[i]


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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    vw = [map(int, input().split()) for _ in range(n)]
    given_vs, given_ws = [list(i) for i in zip(*vw)]
    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        vs = deque()
        ws = deque()
        while True:
            vs.append(given_vs[v - 1])
            ws.append(given_ws[v - 1])
            if v == 1:
                break
            v = v // 2
        print(solve(n, l, list(ws), list(vs)))


if __name__ == '__main__':
    main()