Problem:
 Score : 100 points    Problem Statement There are N flowers arranged in a row.
For each i ( 1 \leq i \leq N ), the height and the beauty of the i -th flower from the left is h_i and a_i , respectively.
Here, h_1, h_2, \ldots, h_N are all distinct.  Taro is pulling out some flowers so that the following condition is met:   The heights of the remaining flowers are monotonically increasing from left to right.   Find the maximum possible sum of the beauties of the remaining flowers.      Constraints  All values in input are integers.  1 \leq N \leq 2 × 10^5  1 \leq h_i \leq N  h_1, h_2, \ldots, h_N are all distinct.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  h_1  h_2  \ldots  h_N  a_1  a_2  \ldots  a_N       Output Print the maximum possible sum of the beauties of the remaining flowers.        Sample Input 1 4
3 1 4 2
10 20 30 40      Sample Output 1 60  We should keep the second and fourth flowers from the left.
Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20 + 40 = 60 .       Sample Input 2 1
1
10      Sample Output 2 10  The condition is met already at the beginning.       Sample Input 3 5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5      Sample Output 4 31  We should keep the second, third, sixth, eighth and ninth flowers from the left.

Solution (Python):
class NumArray(object):

    def __init__(self, nums):
        self.l = len(nums)
        self.tree = [0]*self.l + nums
        for i in range(self.l - 1, 0, -1):
            self.tree[i] = max(self.tree[i<<1],self.tree[i<<1|1])
    
    def update(self, i, val):
        n = self.l + i
        self.tree[n] = val
        while n > 1:
            self.tree[n>>1] = max(self.tree[n],self.tree[n^1])
            n >>= 1
        
    
    def maxRange(self, i, j):
        m = self.l + i
        n = self.l + j
        res = 0
        while m <= n:
            if m & 1:
                
                res = max(res,self.tree[m])
                m += 1
            m >>= 1
            if n & 1 ==0:
                
                res=max(res,self.tree[n])
                n -= 1
            n >>= 1
        return res
    
N=int(input())
H=list(map(int,input().strip().split(" ")))
V=list(map(int,input().strip().split(" ")))
Ans=NumArray([0]*(N+1))
for i in range(len(H)):
    h=H[i]
    ans1=Ans.maxRange(0,h-1)+V[i]
    Ans.update(h,ans1)
print(max(Ans.tree))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): 
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): 
        if r == None: r = self.NN
        if r <= a or b <= l: 
            return -1
        elif a <= l and r <= b : 
            return self.SegTree[k]
        else: 
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): 
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))

Solution (Python):
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = Segtree([0]*(max(H)+1), 0, False)

for h, a in zip(H, A):
    dp.update(h, a+dp.query(0, h))
print(dp.data[1])

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

N += 1


N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(0,0)

for h,a in zip(H,A):
    update(h,query(0,h) + a)

ans = query(0,N+1)
print(ans)

Solution (Python):
class SegTree:
    
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.dep = self.N0.bit_length()
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = max(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return max(a, b)
    
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        for _ in range(self.dep - 1):
            k = (k-1)//2
            self.data[k] = max(self.data[2*k+1], self.data[2*k+2])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = SegTree([0]*(max(H)+1), 0, False)

for h, a in zip(H, A):
    dp.update(h, a+dp.query(0, h))
print(dp.data[0])

Solution (Python):
class SegTree:
    
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = max(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return max(a, b)
    
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0 :
            k = (k-1)//2
            self.data[k] = max(self.data[2*k+1], self.data[2*k+2])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = SegTree([0]*(max(H)+1), 0, False)

for h, a in zip(H, A):
    dp.update(h, a+dp.query(0, h))
print(dp.data[0])

Solution (Python):
class SegTree:
    
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = self.segf(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def segf(self, a, b):
        return max(a, b)
    
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0 :
            k = (k-1)//2
            self.data[k] = self.segf(self.data[2*k+1], self.data[2*k+2])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R-1])
            if L & 1:
                
                s = self.segf(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = SegTree([0]*(max(H)+1), 0, False)

for h, a in zip(H, A):
    dp.update(h, a+dp.query(0, h))
print(dp.data[0])

Solution (Python):


import sys
sys.setrecursionlimit(10**7)
MOD=10**9+7

class Bit:
    def __init__(self, n):
        self.size = n

        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        i+=1
        s = 0
        while i > 0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i+=1

        while i <= self.size:
            self.tree[i] = max(self.tree[i],x)
            i += i & -i




n=int(input())
H = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

modosu = sorted(list(set(H)))
zaatu = {h:j for j,h in enumerate(modosu)}




dp = Bit(n)
for i in range(1,n+1):

    dp.add(zaatu[H[i-1]], dp.sum(zaatu[H[i-1]])+A[i-1])

print(dp.sum(n-1))

Solution (Python):


import sys
sys.setrecursionlimit(10**7)
MOD=10**9+7

class Bit:
    def __init__(self, n):
        self.size = n

        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        i+=1
        s = 0
        while i > 0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i+=1

        while i <= self.size:
            self.tree[i] = max(self.tree[i],x)
            i += i & -i




n=int(input())
H = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

modosu = sorted(list(set(H)))
zaatu = {h:j for j,h in enumerate(modosu)}




dp = Bit(n)
for i in range(1,n+1):

    dp.add(zaatu[H[i-1]], dp.sum(zaatu[H[i-1]])+A[i-1])

print(dp.sum(n-1))

Solution (Python):

from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


class SegmentTree:
    def __init__(self, data, default=0, func=lambda x, y: max(x, y)):
        """initialize the segment tree with data"""
        self._len = _len = len(data)
        self._size = _size = 1 << (_len - 1).bit_length()
        self._data = _data = [default] * (2 * _size)
        self._default = default
        self._func = func
        _data[_size:_size + _len] = data
        for i in reversed(range(_size)):
            _data[i] = func(_data[2 * i], _data[2 * i + 1])

    def __delitem__(self, key):
        self[key] = self._default

    def __getitem__(self, key):
        return self._data[key + self._size]

    def __setitem__(self, key, value):
        key += self._size
        self._data[key] = value
        key >>= 1
        while key:
            self._data[key] = self._func(self._data[2 * key], self._data[2 * key + 1])
            key >>= 1

    def __len__(self):
        return self._len

    def bisect_left(self, value):
        i = 1
        while i < self._size:
            i = 2 * i + 1 if value > self._data[2 * i] else 2 * i
        return i - self._size

    def bisect_right(self, value):
        i = 1
        while i < self._size:
            i = 2 * i + 1 if value >= self._data[2 * i] else 2 * i
        return i - self._size

    def query(self, begin, end):
        begin += self._size
        end += self._size
        res = self._default

        while begin < end:
            if begin & 1:
                res = self._func(res, self._data[begin])
                begin += 1
            if end & 1:
                end -= 1
                res = self._func(res, self._data[end])
            begin >>= 1
            end >>= 1

        return res


def main():
    n = int(input())
    h = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    segtree = SegmentTree([0] * (n + 1))
    for i in range(n):
        x = segtree.query(0, h[i] + 1)
        segtree[h[i]] += x + a[i]

    print(segtree.query(0, n + 1))




BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
class RMQ:
    def __init__(self, n):
        self.n = n 
        self.size = 2**(self.n - 1).bit_length()
        self.data = [0] * (2*self.size-1)

    
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
h = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

rmq = RMQ(2*10**5 + 10)
for i in range(n):
    beaut = rmq.query(0, h[i])
    rmq.update(h[i] - 1, beaut - a[i])
print(-rmq.data[0])

Solution (Python):
class SegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = max(self.node[2*i+1], self.node[2*i+2])

    def get_max(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = max(s, self.node[end])
            if (begin - 1) & 1:
                s = max(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
st = SegmentTree(n+1)

dp = [0]*(n+1)

for i in range(n):
    
    res1 = st.get_max(0, n+1) 
    
    res2 = st.get_max(0, h[i]) + a[i]
    
    dp[i+1] = max(res1, res2)
    st.update(h[i], res2)
print(dp[n])

Solution (Python):
def get(i):
    mx = 0
    while i > 0:
        if bit[i] > mx:
            mx = bit[i]
        i -= i & -i
    return mx


def update(i, x):
    while i < n + 1:
        if x > bit[i]:
            bit[i] = x
        i += i & -i


def f(hs, a_s):
    for h, a in zip(hs, a_s):
        update(h, get(h - 1) + a)
    print(max(bit))


n = int(input())
hs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
bit = [0] * (n + 1)
f(hs, a_s)

Solution (Python):
def get(i):
    mx = 0
    while i > 0:
        if bit[i] > mx:
            mx = bit[i]
        i -= i & -i
    return mx


def update(i, x):
    while i < n + 1:
        if x > bit[i]:
            bit[i] = x
        i += i & -i


def f(n, hs, a_s):
    for h, a in zip(hs, a_s):
        update(h, get(h - 1) + a)
    print(max(bit))


n = int(input())
hs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
bit = [0] * (n + 1)
f(n, hs, a_s)

Solution (Python):
def get(i):
    mx = 0
    while i > 0:
        if bit[i] > mx:
            mx = bit[i]
        i -= i & -i
    return mx


def update(i, x):
    while i < n + 1:
        if x > bit[i]:
            bit[i] = x
        i += i & -i


n = int(input())
hs = list(map(int, input().split()))
a_s = list(map(int, input().split()))

bit = [0] * (n + 1)
for h, a in zip(hs, a_s):
    update(h, get(h - 1) + a)
print(max(bit))

Solution (Python):
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        
        
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    RMQ = SegmentTree([0] * N, merge_func=max, default=0)
    for i in range(N):
        maximum = RMQ.query(0, H[i]-1)
        RMQ.update(H[i]-1, maximum + A[i])
    print(RMQ.query(0, N))


if __name__ == "__main__":
    main()

Solution (Python):


import sys
input = sys.stdin.readline

def f4(n, h, a):
    bit = [0] * (n + 1)

    def getmax(h):
        x = h - 1
        m = 0
        while x != 0:
            if m < bit[x]:
                m = bit[x]
            x -= x & -x
        return(m)

    def update(h, v):
        x = h
        while x <= n:
            if bit[x] < v:
                bit[x] = v
            x += x & -x

    for i in range(1, n + 1):
        m = getmax(h[i])
        update(h[i], m + a[i])
    return(max(bit))

n = int(input()) 
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))

print(f4(n, h, a))

Solution (Python):


import sys
input = sys.stdin.readline

def f4(n, h, a):
    bit = [0] * (n + 1)

    def getmax(h):
        x = h - 1
        m = 0
        while x != 0:
            if m < bit[x]:
                m = bit[x]
            x -= x & -x
        return(m)

    def update(h, v):
        x = h
        while x <= n:
            if bit[x] < v:
                bit[x] = v
            x += x & -x

    for i in range(1, n + 1):
        m = getmax(h[i])
        update(h[i], m + a[i])
    return(max(bit))

n = int(input()) 
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))

print(f4(n, h, a))

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        i1 = 2 * i + 1
        i2 = i1 + 1
        lr = (l + r) // 2
        lmax = getmax(a, b, i1, l, lr)
        rmax = getmax(a, b, i2, lr, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

n = int(input()) 
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f2(n, h, a))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.A[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)>>1
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b):
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1
            r>>=1
        return res

def f(a,b):
    return max(a,b)

n=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))
seg=SegmentTree(n+1,0,f)
for h,a in zip(H,A):
    t=seg.query(0,h)
    seg.update(h,a+t)
print(seg.get_top())

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        i=1
        while 2**i<n:
            i+=1
        self.d=default
        self.leaf=2**i
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.A[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)//2
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b): 
        T=self.tree
        l=a+self.leaf-1
        r=b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1
            r>>=1
        return res

def f(a,b):
    return max(a,b)

n=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))
seg=SegmentTree(n+1,0,f)
for h,a in zip(H,A):
    t=seg.query(0,h)
    seg.update(h,a+t)
print(seg.get_top())

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
h = tuple(map(lambda x:int(x)-1,input().split()))
a = tuple(map(int,input().split()))


def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2


def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -float("inf")
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))



num = 1
while num <= n:
    num *= 2
seg = [0]*(2*num-1)


dp = [a[0]] + [0]*(n-1)
update(h[0],a[0])
for i in range(1,n):
    dp[i] = max(0,query(0,h[i],0,0,num))+a[i]
    update(h[i],dp[i])

print(max(dp))

Solution (Python):
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

h = [0] + h
a = [0] + a

bit = [0] * (n+1)
def update(a, w):
    x = a
    while x <= n:
        bit[x] = max(bit[x], w)
        x += x & -x

def solve(a):
    res = 0
    x = a
    while x > 0:
        res = max(res, bit[x])
        x -= x & -x
    return res

for i in range(1, n+1):
    ma = solve(h[i]-1)
    update(h[i], ma + a[i])

print(max(bit))

Solution (Python):
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

h = [0] + h
a = [0] + a

dp = [0] * (n+1)

bit = [0] * (n+1)
def update(a, w):
    x = a
    while x <= n:
        bit[x] = max(bit[x], w)
        x += x & -x

def solve(a):
    res = 0
    x = a
    while x > 0:
        res = max(res, bit[x])
        x -= x & -x
    return res

for i in range(1, n+1):
    ma = solve(h[i]-1)
    update(h[i], ma + a[i])

print(max(bit))

Solution (Python):


class FenwickTree:
    def __init__(self, size):
        self.elems = [0 for _ in range(size)]
        self.size = len(self.elems)

    def query(self, ind):
        resp = 0
        while ind > 0:
            resp = max(resp, self.elems[ind])
            ind -= ind & -ind
        return resp

    def update(self, ind, val):
        while ind < self.size:
            self.elems[ind] = max(self.elems[ind], val)
            ind += ind & -ind


n = input()
h = map(int, raw_input().split())
a = map(int, raw_input().split())
tree = FenwickTree(n + 1)

dp = [0] * n
for i in range(n):
    dp[i] = a[i] + tree.query(h[i])
    tree.update(h[i], dp[i])
print(max(dp))

Solution (Python):

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import deque
N0 = 2**(N).bit_length()
INF = float("inf")
INF = -(2**31-1) 

data = [INF]*(2*N0)

def update(k,x):
    k += N0 - 1
    data[k] = x
    while k >= 0:
        k = (k-1)//2
        data[k] = max(data[2*k+1], data[2*k+2])


def query(l,r):
    L = l + N0 - 1 
    R = r + N0 - 1
    
    s = INF
    while L < R:
        

        if R & 1 == 0:
            s = max(s, data[R])
            R -= 2
            
            
        else:
            s = max(s, data[R])
            R -= 3

        if L & 1:
            
            s = max(s, data[L])
            
            L -= 1
        else:
            s = max(s,data[L])
            
        L >>= 1; R >>= 1
    if L == R:
        s = max(s,data[L])
    return s

















dp = [0] * (N+1)


for i in range(1,N+1):
    
    dp[i] = max(query(0, H[i-1]), 0) + A[i-1]
    update(H[i-1], dp[i])
print(max(dp))

Solution (Python):

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import deque
N0 = 2**(N).bit_length()
INF = float("inf")
INF = -(2**31-1) 

data = [INF]*(2*N0)

def update(k,x):
    k += N0 - 1
    data[k] = x
    
    
    
    
    while k >= 0:
        k = (k-1)//2
        data[k] = max(data[2*k+1], data[2*k+2])


def query(l,r):
    L = l + N0 
    R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s,data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

dp = [0] * (N+1)


for i in range(1,N+1):
    dp[i] = max(query(0, H[i-1]), 0) + A[i-1]
    update(H[i-1], dp[i])
print(max(dp))

Solution (Python):
N = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

class SegTreeMax:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [0]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = max(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = max(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.nodes[k]
        return max(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

segt = SegTreeMax([0]*N)
ans = 0
for h,a in zip(H,A):
    v = segt.query(0,h) + a
    segt.update(h-1,v)
    ans = max(ans, v)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))



for i in range(30):
    if N<=2**i:
        seg_el=2**i
        break

SEG=[0]*(2*seg_el-1)

def update(n,x,seg_el):
    i=n+seg_el-1
    while i>=0:
        SEG[i]=max(x,SEG[i])
        i=(i-1)//2

def getvalues(a,b,k,l,r):
    if r<=a or b<=l:
        return -float("inf")
    if a<=l and r<=b:
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return max(vl,vr)

for i in range(N):
    h,a=H[i],A[i]
    x=getvalues(0,h,0,0,seg_el)
    update(h-1,x+a,seg_el)

print(getvalues(0,N,0,0,seg_el))