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
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


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


MOD = 10**9 + 7
INF = 2**31  


class SegmentTree:
    def __init__(self, n: int, segfunc=max, identity_element=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.func = segfunc
        self.n_origin = n
        self.num = 2 ** (self.n_origin - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num - 1)  
        
        
        
        

    def __getitem__(self, idx):  
        if isinstance(idx, slice):
            start = idx.start if idx.start else 0
            stop = idx.stop if idx.stop else self.n_origin
            l = start + self.num - 1
            r = l + stop - start
            return self.tree[l:r:idx.step]
        elif isinstance(idx, int):
            i = idx + self.num - 1
            return self.tree[i]

    def update(self, i, x):
        '''
        i番目の要素をxに変更する(木の中間ノードも更新する) O(logN)
        '''
        i += self.num - 1
        self.tree[i] = x
        while i:  
            i = (i - 1) // 2
            self.tree[i] = self.func(self.tree[i * 2 + 1],
                                     self.tree[i * 2 + 2])

    def query(self, l, r):
        '''区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど'''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        res_right = []
        res_left = []
        while l < r:  
            if l & 1:
                res_left.append(self.tree[l - 1])
                l += 1
            if r & 1:
                r -= 1
                res_right.append(self.tree[r - 1])
            l >>= 1
            r >>= 1
        res = self.ide
        
        for x in res_left:
            res = self.func(x, res)
        for x in reversed(res_right):
            res = self.func(res, x)
        return res


'''
dp[i,h] ... 花の美しさの最大値、:iまで考慮したとき、最後の高さhであるようなとり方の場合の

if H[i]<=h: 
    dp[i+1, h] = dp[i,h]
else: 
    dp[i+1, H[i]] = max(dp[i+1,h])+A[i] 

だけど、O(N^2)を処理することはできない！

i->i+1は配列更新にしておいて,
dp[i,:]をsegment treeで持てばok!


もしH[i]足せって問題でも区間更新遅延セグ木で持てば大丈夫そうって示唆がされるね
'''

N = a_int()
H = ints()
A = ints()

dpi = SegmentTree(2 * 10**5 + 1)
for i in range(N):
    ma = dpi.query(0, H[i])
    dpi.update(H[i], ma + A[i])
print(max(dpi[0:2 * 10**5 + 1]))

Solution (Python):
class SegTree():
    
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        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 - 1] = init_val[i]

        for i in range(self.num-2,-1,-1):
            self.tree[i]=self.segfunc(self.tree[2*i+1],self.tree[2*i+2])

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

    
    def query(self,l,r):
        res = self.ide_ele

        l += self.num-1
        r += self.num-2
        while r>=l:
            if l & 1 == 0:
                res = self.segfunc(res,self.tree[l])
            if r & 1 == 1:
                res = self.segfunc(res,self.tree[r])
                r -= 1
            l = l // 2
            r = (r-1) // 2
        return res

N=int(input())
h=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]


dp=[0 for _ in range(N+1)]

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

ide_ele=-100

seg=SegTree(dp,segfunc,ide_ele)

for i in range(0,N):
    x=h[i]
    A=seg.query(0,x+1)
    seg.update(x,A+a[i])


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

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








class SegmentTree:
  arr=None
  tree=None
  n=0
  
  DEF=0
  def __init__(self,arr):
    self.arr=arr
    size=len(arr)
    
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    
    
    
    for i in range(size):
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
  
  def __choose__(self,a,b):
    return max(a,b)
  
  
  def update(self,x,val):
    x+=self.n-1
    
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  
  
  
  def get_val(self,a,b,k=0,l=0,r=-1):
    
    if r<0:
      r=self.n
      
    
    if r<=a or b<=l:
      return self.DEF
    
    
    if a<=l and r<=b:
      return self.tree[k]
    
    
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print(self.tree)
    
N = int(readline())
H = list(map(int,readline().split()))
A = list(map(int,readline().split()))

dp = [0] * (N + 1)
ST = SegmentTree(dp)

for i in range(len(H)):
  h = H[i]
  a = A[i]
  
  maxval = ST.get_val(0,h)
  ST.update(h, maxval + a)

print(ST.get_val(0, N + 1))

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

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

HHtoIND = [[H[i], i] for i in range(n)]
HHtoIND.sort()

INDtoHH = [0] * n
for i in range(n):
    INDtoHH[HHtoIND[i][1]] = i

class segtree_max:  
    def __init__(self, n, f = 0):  
        self.size = n
        i = 1
        while i < n:
            i *= 2
        self.tree = [f] * (2*i-1)
        self.size2 = i
        self.f = f
        
    def update(self, i, x):  
        j = self.size2 + i - 1
        self.tree[j] = x
        while j > 0:
            j = (j-1) // 2
            self.tree[j] = max(self.tree[2*j+1], self.tree[2*j+2])
            
    
    def get(self, a, b, k=0, l=0, r=None):  
        if r == None:
            r = self.size2
        if r <= a or b <= l:
            return self.f
        elif a <= l and r <= b:
            return self.tree[k]
        else:
            
            vl = self.get(a, b, 2*k+1, l, (l+r)//2)
            vr = self.get(a, b, 2*k+2, (l+r)//2, r)
            return max(vl, vr)

T = segtree_max(n)

for i in range(n):
    hh = INDtoHH[i]
    T.update(hh, T.get(0, hh) + A[i])
    

print(T.get(0, n))

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

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

HHtoIND = [[H[i], i] for i in range(n)]
HHtoIND.sort()

INDtoHH = [0] * n
for i in range(n):
    INDtoHH[HHtoIND[i][1]] = i

class segtree:  
    def __init__(self, n):  
        self.size = n
        i = 1
        while i < n:
            i *= 2
        self.tree = [0] * (2*i-1)
        self.size2 = i
        
    def update(self, i, x):  
        j = self.size2 + i - 1
        self.tree[j] = x
        while j > 0:
            j = (j-1) // 2
            self.tree[j] = max(self.tree[2*j+1], self.tree[2*j+2])
            
    
    def get(self, a, b, k=0, l=0, r=None):  
        if r == None:
            r = self.size2
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.tree[k]
        else:
            
            vl = self.get(a, b, 2*k+1, l, (l+r)//2)
            vr = self.get(a, b, 2*k+2, (l+r)//2, r)
            return max(vl, vr)

T = segtree(n)

for i in range(n):
    hh = INDtoHH[i]
    T.update(hh, T.get(0, hh) + A[i])

print(T.get(0, n))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] = val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)

N = I()
H = IL()
A = IL()

ST = SegmentTree(2*10**5,max,0)
for i in range(N):
  h = H[i]
  a = A[i]
  ST.update(h,ST.get(0,h)+a)
  
print(ST.node[1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] = val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)

N = I()
H = IL()
A = IL()

ST = SegmentTree(2*10**5,max,0)
for i in range(N):
  h = H[i]
  a = A[i]
  ST.update(h,ST.get(0,h)+a)
  
print(max(ST.node))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] = val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)

N = I()
H = IL()
A = IL()

ST = SegmentTree(2*10**5,max,0)
for i in range(N):
  h = H[i]
  a = A[i]
  ST.update(h,ST.get(0,h)+a)
  
print(ST.get(0,2*10**5+1))

Solution (Python):

class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def query(self, i):
    s = 0
    while i > 0:
      s = max(s,self.bit[i])
      i -= i & -i
    return s
  def update(self, i, x):
    
    self.el[i] = max(self.el[i],x)
    while i <= self.n:
      self.bit[i] = max(self.bit[i],x)
      i += i & -i

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = BIT(N)
for i in range(N):
  dp.update(H[i],dp.query(H[i]-1)+A[i])
ans = dp.query(N)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] = max(self.bit[x - 1], w)
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res = max(res, self.bit[x - 1])
            x -= x & -x
        return res

n = I()
H = LI()
A = LI()
D = {e:i for i,e in enumerate(sorted(H))}
bit = BIT(n)
for i in range(n):
    idx = D[H[i]]
    bit.add(idx, bit.sum(idx) + A[i])

print(bit.sum(n - 1))

Solution (Python):
class Bit:
    """1-indexed"""

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

    def max(self, i):
        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 solve():
    N = int(input())
    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    S = sorted([(h, i) for i, h in enumerate(H)])

    dp = Bit(N)
    for h, i in S:
        dp.update(i + 1, dp.max(i) + A[i])
    print(dp.max(N))


solve()

Solution (Python):
class Bit:
    """1-indexed"""

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

    def max(self, i):
        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


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

S = sorted([(h, i) for i, h in enumerate(H)])

dp = Bit(N)
for h, i in S:
    dp.update(i + 1, dp.max(i) + A[i])
print(dp.max(N))

Solution (Python):
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))