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:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    n = N.bit_length()
    V = [0]*N; W = [0]*N
    for i in range(N):
        V[i], W[i] = LI()
    q = I()
    Q = [LI()for _ in range(q)]
    ans = [0]*q
    if N<1024:
        S = [[]for _ in range(N)]
        for i in range(N):
            key = i + 1
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            #print(D)
            now = 0
            for j in range(len(D)):
                if now < D[j][1]:
                    now = D[j][1]
                else:
                    D[j] = [D[j][0],now]
            S[i] = D

        for i,[v,l] in enumerate(Q):
            D = S[v-1]
            for j in range(len(D))[::-1]:
                if D[j][0]<=l:
                    ans[i] = D[j][1]
                    break
        for v in ans:
            print(v)
        return


    half = 1<<9
    S = [[] for _ in range(half)]
    for i in range(half//2,half):
        key = i + 1
        cur = []
        while (key > 0):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())
        now = 0
        for j in range(len(D)):
            if now < D[j][1]:
                now = D[j][1]
            else:
                D[j] = [D[j][0],now]
        S[i] = D

    for i,[v,l] in enumerate(Q):
        v -= 1
        key = v + 1
        if key<=512:
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            if D[j][0] <= l:
                if ans[i]<D[j][1]:
                    ans[i] = D[j][1]
            continue
        cur = []
        while (key > 512):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())

        D2 = S[key-1]
        now = len(D2)-1
        for j in range(len(D)):
            while(now>=0 and D2[now][0]+D[j][0]>l):
                now -= 1
            if now==-1:
                break
            if ans[i]<D2[now][1]+D[j][1]:
                ans[i] = D2[now][1]+D[j][1]

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin

readline = stdin.readline

n = int(readline())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 9)

# dp[vertex] = list of (weight, value)
dp[0] = [0 if i < w[0] else v[0] for i in range(max_l + 1)]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = [max(dp[parent][i], dp[parent][i - w[u]] + v[u])
                if i >= w[u] else dp[parent][i]
                for i in range(max_l + 1)]

def solve(u, l):
    if u < len(dp):
        return dp[u][l]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

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

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 10)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend((ww + w[u], vv + v[u]) for ww, vv in dp[parent]
              if ww + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if ls[tail][0] == ls[i][0]:
            ls[tail] = ls[i]
        elif ls[tail][1] < ls[i][1]:
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

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

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend((ww + w[u], vv + v[u]) for ww, vv in dp[parent]
              if ww + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if ls[tail][0] == ls[i][0]:
            ls[tail] = ls[i]
        elif ls[tail][1] < ls[i][1]:
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline

n = int(readline())

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

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 11)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][0] == dp[u][i][0]:
            dp[u][tail] = dp[u][i]
        elif dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline

n = int(readline())

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

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][0] == dp[u][i][0]:
            dp[u][tail] = dp[u][i]
        elif dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline

n = int(readline())

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

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 14)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][0] == dp[u][i][0]:
            dp[u][tail] = dp[u][i]
        elif dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

def main():
    from sys import stdin
    import bisect

    readline = stdin.readline

    n = int(readline())

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

    max_l = 10 ** 5

    # dp table (for some amount)
    dp = [None] * min(n, 2 ** 14)

    # dp[vertex] = list of (weight, value)
    dp[0] = [(0, 0), (w[0], v[0])]

    for u in range(1, len(dp)):
        parent = (u - 1) // 2

        dp[u] = dp[parent].copy()
        for ww, vv in dp[parent]:
            dp[u].append((ww + w[u], vv + v[u]))
        dp[u].sort()

        # remove unnecessary entries
        tail = 0
        for i in range(1, len(dp[u])):
            if dp[u][i][0] > max_l:
                break
            if dp[u][tail][0] == dp[u][i][0]:
                dp[u][tail] = dp[u][i]
            elif dp[u][tail][1] < dp[u][i][1]:
                tail += 1
                dp[u][tail] = dp[u][i]
        del dp[u][tail + 1:]

    dpw = [None] * len(dp)

    def solve(u, l):
        if u < len(dp):
            if not dpw[u]:
                dpw[u] = [w for w, v in dp[u]]
            x = bisect.bisect_right(dpw[u], l) - 1
            return dp[u][x][1]

        parent = (u - 1) // 2
        s = solve(parent, l)
        if l >= w[u]:
            t = v[u] + solve(parent, l - w[u])
            if s < t:
                s = t
        return s

    q = int(readline())
    for i in range(q):
        u, l = map(int, readline().split())
        print(solve(u - 1, l))

main()

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

from sys import stdin
import bisect

n = int(stdin.readline())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 14)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpw = [None] * len(dp)

def solve(u, l):
    if u < len(dp):
        if not dpw[u]:
            dpw[u] = [w for w, v in dp[u]]
        x = bisect.bisect_right(dpw[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(stdin.readline())
for i in range(q):
    u, l = map(int, stdin.readline().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 14)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 16)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 15)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

# dp table (for some amount)
dp = [None] * min(n, 2 ** 15)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

# memoization cache for each vertex
cache = [{} for _ in range(n)]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    if l in cache[u]:
        return cache[u][l]
    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    cache[u][l] = s
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack Queries on a tree

n = int(input())

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

# memoization cache for each vertex
cache = [{} for _ in range(n)]

def solve(u, l):
    if l in cache[u]:
        return cache[u][l]
    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    cache[u][l] = s
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))

Submission status: Time Limit Exceeded

Solution code:
import os,io
from sys import stdout
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
sys.setrecursionlimit(10**7)
import copy
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
dic = {}
q = int(input())
Q = []
lm = 0
for i in range(q):
    a,b = map(int,input().split())
    lm = max(b,lm)
    Q.append((a,b))
d = [-1]*(lm+1)
d[0] = 0
d[min(lm,l[0][1])] = l[0][0]
dic[1] = d
def dfs(x):
    if x in dic:
        return dic[x]
    li = copy.deepcopy(dfs(x//2))
    for i in range(lm-1,-1,-1):
        if li[i] >= 0 and i+l[x-1][1] <= lm:
            s = i+l[x-1][1]
            li[s] = max(li[s],li[i]+l[x-1][0])
    dic[x] = li
    return li

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

Submission status: Time Limit Exceeded

Solution code:
import os,io
from sys import stdout
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
sys.setrecursionlimit(10**7)
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    dic = {}
    q = int(input())
    Q = []
    lm = 0
    for i in range(q):
        a,b = map(int,input().split())
        lm = max(b,lm)
        Q.append((a,b))
    d = [-1]*(lm+1)
    d[0] = 0
    if l[0][1] <= lm:
        d[l[0][1]] = l[0][0]
    dic[1] = d
    def dfs(x):
        if x in dic:
            return dic[x]
        c = [-1]*(lm+1)
        v,w = l[x-1]
        li = dfs(x//2)
        for i in range(lm,-1,-1):
            c[i] = li[i]
            if li[i] >= 0 and i+w <= lm:
                c[i+w] = max(li[i+w],li[i]+v)
        dic[x] = c
        return c

    for a,b in Q:
        s = dfs(a)
        print(max(s[:b+1]))
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
values, weights = zip(*[map(int, input().split()) for _ in range(n)])


def find_ancestors(v):
    res = [v]
    while v != 1:
        v //= 2
        res.append(v)
    return res


q = int(input())
for _ in range(q):
    v, lim = map(int, input().split())
    anc = find_ancestors(v)
    dp = [0]*(lim+1)
    for v in anc:
        val = values[v-1]
        wei = weights[v-1]
        for j in reversed(range(lim+1)):
            if 0 <= j-wei:
                dp[j] = max(dp[j], dp[j-wei]+val)
    print(dp[lim])

Submission status: Time Limit Exceeded

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

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**10)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**10,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

def solve(V,L):
    t=[(0,0)]
    while V>=2**10:
        for v,w in t:
            nv,nw=v+vw[V][0],w+vw[V][1]
            t.append((nv,nw))
        V//=2
    ans=0
    for v,w in t:
        if L>=w:
            ans=max(ans,v+dp[V][L-w])
    return ans

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

Submission status: Time Limit Exceeded

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

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

def solve(V,L):
    t=[(0,0)]
    while V>=2**9:
        for v,w in t:
            nv,nw=v+vw[V][0],w+vw[V][1]
            t.append((nv,nw))
        V//=2
    ans=0
    for v,w in t:
        if L>=w:
            ans=max(ans,v+dp[V][L-w])
    return ans

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

Submission status: Time Limit Exceeded

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

input = sys.stdin.buffer.readline

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

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))

Submission status: Time Limit Exceeded

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

input = sys.stdin.buffer.readline

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

n = min(2**10, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))