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):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()











class SegTree:
    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.size=n
        self.ide_ele=ide
        self.num=1<<(self.size-1).bit_length()
        self.table=[self.ide_ele]*2*self.num
        self.index=[0]*2*self.num
        self.lazy=[self.ide_ele]*2*self.num
        self.func=function
        
        if not hasattr(init_val,"__iter__"):
            init_val=[init_val]*self.size
        for i,val in enumerate(init_val):
            self.table[i+self.num-1]=val
            self.index[i+self.num-1]=i
        
        for i in range(self.num-2,-1,-1):
            self.table[i]=self.func(self.table[2*i+1],self.table[2*i+2])
            if self.table[i]==self.table[i*2+1]:
                self.index[i]=self.index[i*2+1]
            else:
                self.index[i]=self.index[i*2+2]

    def __iter__(self):
        return iter(self.table[self.num-1:self.num-1+self.size])

    def __getitem__(self,key):
        return self.table[key+self.num-1]

    def __setitem__(self,key,value):
        self.update(key,value)

    def update(self,k,x):
        k+=self.num-1
        self.table[k]=x
        while k:
            k=(k-1)//2
            res=self.func(self.table[k*2+1],self.table[k*2+2])
            self.table[k]=res
            
            
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
            
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
            if q&1==1:
                res=self.func(res,self.table[q])
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
        return res
    
    def query_id(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        idx=p
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
                if res==self.table[p]:
                    idx=self.index[p]
            if q&1==1:
                res=self.func(res,self.table[q])
                if res==self.table[q]:
                    idx=self.index[q]
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
            if res==self.table[p]:
                idx=self.index[p]
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
            if res==self.table[p]:
                idx=self.index[p]
            elif res==self.table[q]:
                idx=self.index[q]
        return idx

    def __str__(self):
        
        rt=self.table[self.num-1:self.num-1+self.size]
        return str(rt)

show_flg=False
show_flg=True

ans=0

n=I()
h=LI()
a=LI()

st=SegTree(n+1,init_val=0,function=max,ide=-inf)

for i in range(n):
    c=h[i]
    v=a[i]
    st[c]=max(st[c],a[i],st.query(0,c)+v)
print(max(st))

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()











class SegTree:
    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.size=n
        self.ide_ele=ide
        self.num=1<<(self.size-1).bit_length()
        self.table=[self.ide_ele]*2*self.num
        self.index=[0]*2*self.num
        self.lazy=[self.ide_ele]*2*self.num
        self.func=function
        
        if not hasattr(init_val,"__iter__"):
            init_val=[init_val]*self.size
        for i,val in enumerate(init_val):
            self.table[i+self.num-1]=val
            self.index[i+self.num-1]=i
        
        for i in range(self.num-2,-1,-1):
            self.table[i]=self.func(self.table[2*i+1],self.table[2*i+2])
            if self.table[i]==self.table[i*2+1]:
                self.index[i]=self.index[i*2+1]
            else:
                self.index[i]=self.index[i*2+2]
        
    def update(self,k,x):
        k+=self.num-1
        self.table[k]=x
        while k:
            k=(k-1)//2
            res=self.func(self.table[k*2+1],self.table[k*2+2])
            self.table[k]=res
            
            
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
            
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
            if q&1==1:
                res=self.func(res,self.table[q])
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
        return res
    
    def query_id(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        idx=p
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
                if res==self.table[p]:
                    idx=self.index[p]
            if q&1==1:
                res=self.func(res,self.table[q])
                if res==self.table[q]:
                    idx=self.index[q]
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
            if res==self.table[p]:
                idx=self.index[p]
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
            if res==self.table[p]:
                idx=self.index[p]
            elif res==self.table[q]:
                idx=self.index[q]
        return idx

    def __str__(self):
        
        rt=self.table[self.num-1:self.num-1+self.size]
        return str(rt)

show_flg=False
show_flg=True

ans=0

n=I()
h=LI()
a=LI()

st=SegTree(n+1,init_val=0,function=max,ide=-inf)

for i in range(n):
    c=h[i]
    v=a[i]
    x=max(st.query(c,c+1),a[i],st.query(0,c)+v)
    st.update(c,x)

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

Solution (Python):
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s

def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = SegTree([0] * N, max)

    for h, a in zip(H, A):
        S.update(h - 1, S.query(0, h - 1) + a)
    return S.query(0, N)

print(main())

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


class SegmentTreeRMQ(object):  
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        

    def get(self, i):
        return self.array[i + self.len]

    def get_maximum(self, l, r):
        L = l+self.len
        R = r+self.len
        ANS = -1 << 30

        while L < R:
            if L & 1:
                ANS = max(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = max(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


N = ni()
h_array = na()
a_array = na()

ans = SegmentTreeRMQ(N+1, 0)



for h, a in zip(h_array, a_array):
    tmp = ans.get_maximum(0, h) + a
    if ans.get(h) < tmp:
        ans.update(h, tmp)

print(ans.get_maximum(0, N+1))

Solution (Python):
import operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0
 
        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn
 
        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1
 
    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value
 
        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])
 
    def update(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))
 
    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]
 
        L = 0 if L is None else L
        r = self._size if r is None else r
 
        if from_i <= L and r <= to_i:
            return self._tree[k]
 
        if to_i <= L or r <= from_i:
            return None
 
        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)
 
    def __len__(self):
        return self._size
 
 
def resolve():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
 
    Flowers = []
    for i in range(N):
        Flowers.append((H[i], (A[i], i)))
    
    Flowers.sort()
 
    seg = SegmentTree(N, fn=max)
    for i in range(N):
        h, (a, idx) = Flowers[i]
        maxV = seg.get(0, idx)
        
        if maxV == None:
            maxV = 0
        seg.set(idx, maxV+a)
 
    ans = seg.get(0, N)
    print(ans)
    
if __name__ == "__main__":
    resolve()

Solution (Python):



from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, HS, VS):
    bit = [0] * (N + 1)  

    def bit_put(pos, val):
        assert pos > 0
        x = pos
        while x <= N:
            bit[x] = max(bit[x], val)
            x += x & -x  

    def bit_max(pos):
        assert pos > 0
        ret = 0
        x = pos
        while x > 0:
            ret = max(ret, bit[x])
            x -= x & -x
        return ret

    for i in range(N):
        h = HS[i]
        m = bit_max(h)
        bit_put(h, m + VS[i])

    return bit_max(N)


def main():
    
    N = int(input())
    HS = list(map(int, input().split()))
    VS = list(map(int, input().split()))
    print(solve(N, HS, VS))



T1 = """
4
3 1 4 2
10 20 30 40
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    60
    """


T2 = """
1
1
10
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    10
    """


T3 = """
5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    5000000000
    """


T4 = """
9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    31
    """



def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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




class SegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : nより大きい最小の2のべき乗
        """
        if 2**(n.bit_length()-1)==n:
            self.num = n
        else:
            self.num = 2**n.bit_length()
        self.seg = [0] * (2*self.num-1)
        if a is not None:
            for i,item in enumerate(a):
                self.update(i,item)
        
    def update(self,i,x):
        """update(i,x):Aiをxに更新する
        """
        k = i + self.num - 1
        while k >= 0:
            if x>self.seg[k]:
                self.seg[k] = x
                k = (k-1)//2
            else:
                break
                
    def query(self,a,b,k=0,l=0,r=None,index=False):
        """query(a,b,0,0,num):[a,b)の最大値
        index==Trueのときインデックスも返す
        """
        if r is None:
            r = self.num

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

st = SegmentTree(n+1)
for item, aa in zip(h,a):
    val = st.query(0,item)
    st.update(item, val+aa)
print(max(st.seg))

Solution (Python):
class Segtree():  

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

    def __init__(self, LIST, ide_ele):  
        n = len(LIST)
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):  
            self.tree[self.num + i] = LIST[i]
        for i in range(self.num - 1, 0, -1):  
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):  
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):  
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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

dp = Segtree([0] * (n + 1), 0)
for ai, hi in zip(a, h):
    dp.update(hi, dp.query(0, hi) + ai)
print(dp.query(0, n + 1))

Solution (Python):
class Max_Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = 0  
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i
def main():
    N = int(input())
    *H, = map(int, input().split())
    *A, = map(int, input().split())
    
    dp = Max_Bit(N)
    sort_H_i = sorted((h, i) for i, h in enumerate(H))
    for h, i in sort_H_i:
        dp.update(i+1, dp.get_max(i) + A[i])
    print(dp.get_max())

if __name__ == '__main__':
    main()

Solution (Python):
class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = 0  
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i
def main():
    """
    dp: 花iを使うとした場合の1からiまでつかった美しさの最大値
    短い花から更新する

    """
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = Max_Bit(N)
    sort_H_i = sorted((h, i) for i, h in enumerate(H))
    for h, i in sort_H_i:
        dp.update(i+1,dp.get_max(i) + A[i])
    print(dp.get_max())

if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal


















def inp():
    return(int(input()))
def inlt(): 
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def insr2():
    s = input()
    return((s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))



def seg_fun(fun,a,b):
    if fun == "max":
        return max(a,b)
    elif fun == "min":
        return min(a,b)
    elif fun == "sum":
        return a+b
def build_seg_tree(arr,n,fun) : 
    
    tree = [ 0 for i in range(2*n)]
    for i in range(n) :  
        tree[n + i] = arr[i]  
    
    for i in range(n - 1, 0, -1) :  
        tree[i] = seg_fun(fun,tree[i << 1],tree[i << 1 | 1])
        
    return tree  
  

def updateTreeNode(p, value,tree,n,fun) :  
    
    tree[p + n] = value;  
    p = p + n;  
    
    i = p
    while i > 1 : 
        tree[i >> 1] = seg_fun(fun,tree[i],tree[i ^ 1])
        
        i >>= 1;  
    return tree
  

def query(l, r,tree,n,fun) :  
    if fun == "max":
        res = -1*sys.maxsize
    if fun == "min":
        res = sys.maxsize
    if fun == "sum":
        res = 0
    
    l += n; 
    r += n; 
    while l < r : 
        if (l & 1) : 
            
            res = seg_fun(fun,res,tree[l])
            l += 1
      
        if (r & 1) : 
            r -= 1
            
            res = seg_fun(fun,res,tree[r])
              
        l >>= 1
        r >>= 1
      
    return res;  


def pr_list(a):
    print(*a, sep=" ")
def main():
	
    tests = 1
    mod = 1000000007
    limit = 10**18
    ans = 0
    for test in range(tests):
        n = inp()
        h = inlt()
        a= inlt()
        dp = [-1*sys.maxsize for i in range(n+1)]
        tree = build_seg_tree(dp,len(dp),"max")
        
        ans = 0
        for i in range(0,n):
            dp[h[i]] = max(0, query(0, h[i],tree,len(dp),"max")) + a[i]
            ans = max(dp[h[i]],ans)
            tree = updateTreeNode(h[i], dp[h[i]],tree,len(dp),"max")
            

    print(ans)
if __name__== "__main__":
	main()

Solution (Python):
from sys import stdin,stdout 
from bisect import bisect,bisect_left,bisect_right
def gt(): return map(int, stdin.readline().split())
def gi(): return int(stdin.readline())
def gl(): return list(map(int, stdin.readline().split())) 
def gs(): return stdin.readline()
def getmax(BITTree,i): 
    s = 0
    i = i+1
    while i > 0:
        s = max(s,BITTree[i])
        i -= i & (-i) 
    return s 

def updatebit(BITTree , n , i ,v): 
    i += 1
    while i <= n: 
        BITTree[i] = max(v,BITTree[i]) 
        i += i & (-i) 
def construct( n): 
    BITTree = [0]*(n+1) 
    
    
    return BITTree 
n=gi()
h=gl()
a=gl() 
m=max(h)
BITTree = construct(m+1)
for i in range(n):
    updatebit(BITTree,m+1,h[i],getmax(BITTree,h[i]-1)+a[i])
ans=0
print(getmax(BITTree,m))

Solution (Python):
n = int(input())
h = list(map(int,input().split()))
h1 = [[h[i],i] for i in range(n)]
h1.sort()
a = list(map(int,input().split()))
dp = [0]*n
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    def max(self, i):
        
        s = 0
        i += 1
        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(x,self.tree[i])
            i += i & -i
bit = Bit(2*n+1)

for i in range(n):
    s = h1[i][1]
    x = a[s]+bit.max(s-1)
    dp[s] = x
    bit.add(s,x)
    
print(max(dp))

Solution (Python):
def solve():
    N = int(input())
    Hs = list(map(int, input().split()))
    As = list(map(int, input().split()))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            if A > data[iB]:
                data[iB] = A
            iB += iB & -iB
    def getMax(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            if data[iB] > ans:
                ans = data[iB]
            iB -= iB & -iB
        return ans


    iHs = list(range(N))
    iHs.sort(key=lambda iH: Hs[iH])
    odrHs = [0]*(N)
    for odrH, iH in enumerate(iHs):
        odrHs[iH] = odrH

    data, numPow2 = makeBIT(N)

    ans = 0
    for odrH in range(N):
        iH = iHs[odrH]
        v = As[iH] + getMax(iH)
        if v > ans:
            ans = v
        setValue(iH, v)

    print(ans)


solve()

Solution (Python):
def solve():
    N = int(input())
    Hs = list(map(int, input().split()))
    As = list(map(int, input().split()))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            if A > data[iB]:
                data[iB] = A
            iB += iB & -iB
    def getMax(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            if data[iB] > ans:
                ans = data[iB]
            iB -= iB & -iB
        return ans


    iHs = list(range(N))
    iHs.sort(key=lambda iH: Hs[iH])
    odrHs = [0]*(N)
    for odrH, iH in enumerate(iHs):
        odrHs[iH] = odrH

    data, numPow2 = makeBIT(N)

    ans = 0
    for iH in range(N):
        odrH = odrHs[iH]
        v = As[iH] + getMax(odrH)
        if v > ans:
            ans = v
        setValue(odrH, v)

    print(ans)


solve()