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):
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

num = 2
while num <= N+1:
    num *= 2

seg = [0]*(2*num-1)


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 -1
    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))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))

Solution (Python):
class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
    
    def __init__(self, a): 
        n = len(a)
        self.ide_ele = 0 
        self.num = 2**((n-1).bit_length()) 
        self.seg = [self.ide_ele]*2*self.num
        
        
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    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.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * N
S = SegmentTree(dp)
for i in range(N):
    tmp = S.query(0,h[i]-1)
    S.update(h[i]-1, tmp+a[i])
print(S.query(0,N))

Solution (Python):
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, i, x):
        self.b[i + self.n - 1] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))

Solution (Python):
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/dp/tasks/dp_q
いわゆるインラインdpなのは分かった
→どこが？

dpを決めると、更新式がセグ木などで更新可能？
dp[i][h] = i番目まで見て、最大の高さがhの時の美しさの総和の最大値

dp[i][h] = max( dp[i-1][0] , dp[i-1][1] , … , dp[i-1][h-1] ) + a[i]
なので,RMQで処理できる
→これがインラインdpなのか？？

"""

def make_ST(n,first): 

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): 

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = max(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): 

    if r <= a or b <= l: 
        return 0
    
    if a <= l and r <= b: 
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return max(c1,c2)


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

tree = make_ST(N+1,0)

for i in range(N):

    maxi_sc = RMQ_query(0,h[i],0,0,(len(tree)+1)//2,tree)
    RMQ_update_point(maxi_sc+a[i] , h[i] ,tree)

print (RMQ_query(0,N+1,0,0,(len(tree)+1)//2,tree))

Solution (Python):
ide = 0
def func(a,b):
  return max(a,b)
class SegmentTree:
  def __init__(self,ls,commutative = True):
    if commutative == True:
      self.n = len(ls)
      self.tree = [ide for i in range(self.n)]+ls
    else:
      self.n = 2**((len(ls)-1).bit_length())
      self.tree = [ide for i in range(self.n)]+ls+[ide for i in range(self.n-len(ls))]
    for i in range(1,self.n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def getall(self):
    return self.tree[1]
  def get(self,l,r):
    lret = ide
    rret = ide
    l += self.n
    r += self.n
    while l < r:
      if l&1:
        lret = func(lret,self.tree[l])
        l += 1
      if r&1:
        rret = func(self.tree[r-1],rret)
      l >>= 1
      r >>= 1
    ret = func(lret,rret)
    return ret
  def update(self,i,x):
    i += self.n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])

n = int(input())
h = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [0 for i in range(n+1)]
ST = SegmentTree(dp)
for i in range(1,n+1):
  hi = h[i-1]
  bi = b[i-1]
  x = ST.get(0,hi)
  ST.update(hi,x+bi)
print(ST.getall())

Solution (Python):
def main():
    n = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x >= y:
            return x
        else:
            return y

    def init(init_val):
        
        for i in range(n+1):
            seg[i+num-1] = init_val[i]
        
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while p < q:
            if p&1 == 0: 
                res = segfunc(res, seg[p])
            if q&1 == 1: 
                res = segfunc(res, seg[q])
                q -= 1 
            p = p//2 
            q = (q-1)//2 
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    
    ide_ele = 0

    
    num = 2**n.bit_length()
    seg = [ide_ele]*2*num

    X = [0]*(n+1)
    for i in range(n):
        update(H[i], query(0, H[i]+1)+A[i])
    print(query(0, n+2))

if __name__ == '__main__':
    main()

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

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
        
    def init(init_val):
        for i in range(N+1):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = max(seg[2*i+1],seg[2*i+2])
    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(query(0,N+1))

if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    
    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(query(0,N+1))

if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    
    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(max(dp))

if __name__ == "__main__":
    main()

Solution (Python):
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, index, x):
        index += self.n - 1
        self.tree[index] = x
        while index:
            index = (index - 1) // 2
            self.tree[index] = self.func(self.tree[2 * index + 1], self.tree[2 * index + 2])

    def query(self, left, right):
        if right <= left:
            return self.ie
        left += self.n - 1
        right += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while right - left > 1:
            if left & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right], tmp_r)
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            tmp_l = self.func(tmp_l, self.tree[left])
        else:
            tmp_l = self.func(self.func(tmp_l, self.tree[left]), self.tree[right])
        return self.func(tmp_l, tmp_r)

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

arr = [0 for _ in range(N + 1)]
dp = SegmentTree(arr, max, 0)

for i in range(N):
    dp.set(H[i], dp.query(0, H[i]) + A[i])

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

Solution (Python):
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * (n + 1)
bit = [0] * (n + 1)
for x, y in zip(h, a):
    a = x
    t = 0
    while a > 0:
        t = max(t, bit[a])
        a -= a & -a
    t += y
    dp[x] = t
    while x <= n:
        bit[x] = max(bit[x], t)
        x += x & -x
x = n
ans = 0
while x > 0:
    ans = max(ans, bit[x])
    x -= x & -x
print(ans)

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

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

def init_max(init_max_val):
    
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


ide_ele_max = 0


num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max




dp = [0]*n

for i in range(n-1):
    tmp = query_max(0,h[i]) + a[i]
    if tmp + a[i] > dp[h[i]]:
        dp[h[i]] = tmp
        update_max(h[i],tmp)

print(query_max(0,n))

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

    def bitmax(self, i):
        ret = 0
        while i:
            ret = max(ret, self.tree[i])
            i ^= i & -i
        return ret

    def bitadd(self, i, x):  
        while i <= self.size:
            if self.tree[i] >= x:
                break
            self.tree[i] = x
            i += i & -i
        return
      
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
b = BIT(max(h) + 5)
for x, y in zip(h, a):
    b.bitadd(x, b.bitmax(x) + y)
print(b.bitmax(max(h)))

Solution (Python):


def main():
    import sys

    def input(): return sys.stdin.readline().strip()
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
    
    def query(i):
        s = intv
        i += 1
        while i > 0:
            s = max(s, tree[i-1])
            i -= i & -i
        return s
    
    def update(i, x):
        i += 1
        while i <= size:
            tree[i-1] = max(tree[i-1], x)
            i += i & -i

    n = INT()
    H = LIST()
    A = LIST()

    n += 2
    nv = 1
    while nv < n:
        nv *= 2
    size = nv
    intv = 0
    tree = [intv] * nv

    for h, a in zip(H, A):
        mx = query(h)
        update(h, mx + a)
    ans = query(n)
    print(ans)
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
class SegmentTree:
    def __init__(self, arr, function):
        self.tree = [None for _ in range(len(arr))] + arr
        self.size = len(arr)
        self.fn = function
        self.build_tree()

    def build_tree(self):
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.fn(self.tree[i * 2], self.tree[i * 2 + 1])

    def update(self, p, v):
        p += self.size
        self.tree[p] = v
        while p > 1:
            p = p // 2
            self.tree[p] = self.fn(self.tree[p * 2], self.tree[p * 2 + 1])

    def query(self, l, r):
        l, r = l + self.size, r + self.size
        res = None
        while l <= r:
            if l % 2 == 1:
                res = self.tree[l] if res is None else self.fn(res, self.tree[l])
            if r % 2 == 0:
                res = self.tree[r] if res is None else self.fn(res, self.tree[r])
            l, r = (l + 1) // 2, (r - 1) // 2
        return res

n=int(input())
h=list(map(int,input().split()))
b=list(map(int,input().split()))
new_arr=[]
for i in range(n):
    new_arr.append([h[i],b[i],i])
new_arr.sort(key=lambda x: x[0])
new_arr=new_arr[::-1]

ans=[0 for i in range(n)]
seg=SegmentTree(ans,max)

for seq in new_arr:
    idx=seq[2]
    new_value=seg.query(idx,n-1)
    new_value+=seq[1]
    
    seg.update(idx,new_value)
mx=seg.query(0,n-1)
print(mx)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i

N = INT()
H = LIST()
A = LIST()

bit = BIT(N+1, max, 0)
for h, a in zip(H, A):
    
    mx = bit.query(h)
    
    bit.update(h, mx + a)
ans = bit.query(N)
print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())
d=[0]*-~n
for h,a in zip(a,a[n:]):
 i,s=h,0
 while i:s=max(s,d[i]);i-=i&-i
 while h<=n:d[h]=max(d[h],s+a);h+=h&-h
print(max(d))

Solution (Python):
n,*a=map(int,open(0).read().split())
d=[0]*-~n
for h,a in zip(a,a[n:]):
    i,s=h,0
    while i:
        s=max(s,d[i])
        i-=i&-i
    s+=a
    i=h
    while i<=n:
        d[i]=max(d[i],s)
        i+=i&-i
print(max(d))

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    dp=[0]*-~n
    for h,a in zip(map(int,input().split()),map(int,input().split())):
        i,s=h,0
        while i:
            t=dp[i]
            if t>s:s=t
            i-=i&-i
        s+=a
        i=h
        while i<=n:
            if s>dp[i]:dp[i]=s
            i+=i&-i
    print(max(dp))
main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    dp=[0]*-~n
    for h,a in zip(map(int,input().split()),map(int,input().split())):
        i,s=h,0
        while i:
            t=dp[i]
            if t>s:s=t
            i-=i&-i
        s+=a
        i=h
        while i<=n:
            if s>dp[i]:dp[i]=s
            i+=i&-i
    print(max(dp))
main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())+1
    dp=[0]*n*2
    for h,a in zip(map(int,input().split()),map(int,input().split())):
        l,r,s=n,h+n,0
        while l<r:
            if l&1:
                t=dp[l]
                if t>s:s=t
                l+=1
            if r&1:
                r-=1
                t=dp[r]
                if t>s:s=t
            l>>=1
            r>>=1
        s+=a
        i=h+n
        if s>dp[i]:
            dp[i]=s
            i>>=1
            while i:
                s,t=dp[i+i],dp[i-~i]
                if t>s:s=t
                if s>dp[i]:dp[i]=s
                else:break
                i>>=1
    print(dp[1])
main()

Solution (Python):
class SegTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    n,*a=map(int,open(0).read().split())
    dp=SegTree(n+1,0,lambda a,b:a if a>b else b)
    for h,a in zip(a,a[n:]):dp.update(h,dp.query(0,h)+a)
    print(dp.data[1])
main()

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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))

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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))

Solution (Python):

from collections import Counter
import sys

sys.setrecursionlimit(10**6)


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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))

Solution (Python):

from collections import Counter
import sys

sys.setrecursionlimit(10**6)


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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for h, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))