Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=max):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * (2 * self.n)

        for i in range(self.n):
            self.tree[i+self.n] = seq[i]

        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree([0] * (n+1), op=max)

    for pos, b in zip(heights, beauty):
        best = dp.query(0, pos)
        dp.modify(pos, best + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * (2 * n)
        self.n = n

    def modify(self, pos, val):
        tree = self.tree
        pos += self.n
        tree[pos] = val
        while pos > 1:
            tree[pos//2] = max(tree[pos], tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = max(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = max(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree(n+1)
    for h, b in zip(heights, beauty):
        _max = dp.query(0, h)
        dp.modify(h, _max + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]

dp = list(beauty)

for i in range(n):
    max_beauty = beauty[i]
    for j in range(i):
        if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
            max_beauty = beauty[i] + dp[j]

    dp[i] = max_beauty

ans = max(dp)
print(ans)


Fixed submission:
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)