Problem p02648 (python)

Fixed submission:
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + V_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        V.append(v)
        W.append(w)
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v-1][L]
            v_tmp = [0] * (1 << cnt)
            w_tmp = [0] * (1 << cnt)
            for b in range(1, 1 << cnt):
                lsb = b & -b
                l = lsb.bit_length()
                w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v-1][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        V.append(v)
        W.append(w)
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v][L]
            v_tmp = [0] * (1 << cnt)
            w_tmp = [0] * (1 << cnt)
            for b in range(1, 1 << cnt):
                lsb = b & -b
                l = lsb.bit_length()
                w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp_[j - w] + v:
                    dp_[j] = dp_[j - w] + v
            dp.append(dp_)
            V.append(v)
            W.append(w)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v][L]
            v_tmp = [0] * (1 << cnt)
            w_tmp = [0] * (1 << cnt)
            for b in range(1, 1 << cnt):
                lsb = b & -b
                l = lsb.bit_length()
                w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                if dp_[j] < dp[half][j - w] + v:
                    dp_[j] = dp[half][j - w] + v
            dp.append(dp_)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
        else:
            cnt = 0
            v_ = []
            w_ = []
            while v > m:
                v_.append(V[v-1])
                w_.append(W[v-1])
                v >>= 1
                cnt += 1
            ret = dp[v][L]
            v_tmp = [0] * (1 << cnt)
            w_tmp = [0] * (1 << cnt)
            for b in range(1, 1 << cnt):
                lsb = b & -b
                l = lsb.bit_length()
                w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
                if w_tmp[b] <= L:
                    v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                    ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
            print(ret)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1)]
    
    for i in range(1, n+1):
        v, w = LI()
        half = i >> 1
        dp_ = dp[half][:]
        if i <= m:
            for j in range(maxL+1):
                if j < w:
                    dp_[j] = dp[half][j]
                else:
                    dp_[j] = max(dp[half][j], dp[half][j - w] + v)
            dp.append(dp_)
        else:
            V.append(v)
            W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = LI()
        if i > n:
            V.append(v)
            W.append(w)
            continue
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp-1][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp-1][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = LI()
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp-1][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp-1][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    m = min(n, 1 << 10)
    maxL = 10**5
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = LI()
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = 0
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[v][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = dp[tmp][L]
    for j in range(1, 1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = 0
    for j in range(1 << cnt):
        weight_sum = 0
        value_sum = 0
        idx = j
        for v, w in zip(v_, w_):
            if idx & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(v[tmp-1])
        w_.append(w[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = 0
    for j in range(1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

m = min(n, 1 << 10)
dp = [[0]*(10**5 + 1) for _ in range(m + 1)]
for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(10**5+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)

q = I()
bl = m.bit_length()
for i in range(q):
    v, L = LI()
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - bl
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1 
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>2][j]
        else:
            dp[i][j] = max(dp[i>>2][j], dp[i>>2][j - w] + v)

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp >>= 1
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

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

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

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

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1 
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

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

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        for k in range(x):
            if j >> k & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

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

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        for k in range(x):
            if j >> k & 1:
                weight_sum += W[tmp - 1]
                value_sum += V[tmp - 1]
            tmp //= 2
        if weight_sum > L:
            continue
        value_sum += dp[tmp][L - weight_sum]
        ret = max(ret, value_sum)
    print(ret)