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.



Sample input:
4
3 1 4 2
10 20 30 40


Sample output:
60

Submission status: Accepted

Solution code:
N = int(input())
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
dp = [0] * (N + 1)
#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num = 2 ** (N).bit_length()
seg = [ide_ele] * 2 * num

def segfunc(x, y):
  return max(x, y) #ここ判定関数（ただし結合則があるもの）

def init(init_val):
  #set_val
  for i in range(N):
    seg[i + num - 1] = init_val[i]    
  #built
  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 + 1:
    k = (k - 1) // 2
    seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])
    
def query(p, q):
  if q <= p:
    return ide_ele
  p += num - 1
  q += num - 2
  res = ide_ele
  while q - p > 1:
    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


for i in range(N):
  temp = query(0, h[i + 1]) + a[i + 1]
  update(h[i + 1], temp)
print(query(0, N + 2))

Submission status: Accepted

Solution code:
INF = 10**30

class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[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)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)

#print(dp.node)
print(dp.Get(0, n))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return

#E
def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)
#F
def F():

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    bfs = [1]*n
    bfs[0] = 0
    q = deque([0])
    par = [None]*n
    d = [[0,i] for i in range(n)]
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                par[y] = x
                d[y][0] = d[x][0]+1
                q.append(y)
    d.sort(key = lambda x:-x[0])
    for _,x in d[:-1]:
        px = par[x]
        fx,gx = f[x],g[x]
        f[px] *= fx+gx
        if f[px] >= mod:
            f[px] %= mod
        g[px] *= fx
        if g[px] >= mod:
            g[px] %= mod
    print((f[0]+g[0])%mod)
    return

#G
def G():
    class SegmentTree:
        def __init__(self, size, default, op = max):
            self.size = 2**size.bit_length()
            self.dat = [default]*(self.size*2)
            self.op = op

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

        def add(self, i, x):
            i += self.size
            self.dat[i] = self.op(self.dat[i], x)
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i], x)

        def get(self, a, b = None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            res = None
            while l < r:
                if l & 1:
                    if res is None:
                        res = self.dat[l]
                    else:
                        res = self.op(res, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    if res is None:
                        res = self.dat[r]
                    else:
                        res = self.op(res, self.dat[r])
                l >>= 1
                r >>= 1
            return res
    n = I()
    h = LI()
    a = LI()
    dp = SegmentTree(n+1, 0)
    for i in range(n):
        hi,ai = h[i],a[i]
        ma = dp.get(0,hi)
        dp.update(hi,ma+ai)
    print(dp.get(0,n+1))
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    G()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
H = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

# BIT で、各高さに対して、（最後がその高さの場合の最大値）を管理
def BIT_update(tree,h,x):
    while h <= N and tree[h] < x:
        tree[h] = x
        h += h&(-h)

def BIT_max(tree,h):
    x = 0
    while h:
        y = tree[h]
        x = x if x > y else y
        h -= h&(-h)
    return x

tree = [0] * (N+1)
for h,a in zip(H,A):
    x = BIT_max(tree,h)
    BIT_update(tree,h,x+a)

answer = max(tree)
print(answer)

Submission status: Accepted

Solution code:
def update(fen, pos, value):
    size = len(fen)
    while pos < size:
        fen[pos] = max(fen[pos], value)
        pos = pos + (pos & -pos)

def query(fen, pos):
    ret  = 0
    while pos > 0:
        ret = max(ret, fen[pos])
        pos = pos - (pos & -pos)
    return ret

def main():
    N = int(input())
    H = list(map(int, input().split()))
    B = list(map(int, input().split()))
    fen = list(0 for i in range(0,N + 2))
    ans = 0
    for i in range( 0, N ):
        ret = query(fen, H[i] - 1) + B[i]
        ans = max(ans, ret)
        update(fen, H[i], ret)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def build(t,arr,v,tl,tr):
    if tl == tr:
        t[v] = arr[tl]
    else:
        tm = (tl+tr)//2
        build(t,arr,2*v,tl,tm)
        build(t,arr,2*v+1,tm+1,tr)
        t[v] = max(t[2*v],t[2*v+1])

def maxQuery(t,v,tl,tr,l,r):
    if l > r:
        return 0
    if l == tl and r == tr:
        return t[v]
    tm = (tl+tr)//2
    return max(maxQuery(t,2*v,tl,tm,l,min(r,tm)),maxQuery(t,2*v+1,tm+1,tr,max(l,tm+1),r))

def update(t,v,tl,tr,pos,new_val):
    if tl == tr:
        t[v] = new_val
    else:
        tm = (tl+tr)//2
        if pos <= tm:
            update(t,2*v,tl,tm,pos,new_val)
        else:
            update(t,2*v+1,tm+1,tr,pos,new_val)
        t[v] = max(t[2*v],t[2*v+1])

def create(n,arr):
    t = [0]*4*n
    build(t,arr,1,0,n-1)

    return t
    

def main():
    n = int(raw_input())
    hts = list(map(int,raw_input().split()))
    beauties = list(map(int,raw_input().split()))
    flowers = {}
    for i in range(n):
        flowers[hts[i]] = beauties[i]

    dp = [0]*n
    t = create(n,dp)
    for i in range(n-1,-1,-1):
        curr = hts[i]
        max_val = maxQuery(t,1,0,n-1,curr-1,n-1)
        dp[curr-1] += flowers[curr]+max_val
        update(t,1,0,n-1,curr-1,dp[curr-1])
        #print(t)

    print(max(t))


main()

Submission status: Accepted

Solution code:
# @author 

import sys

class QFlowers:
    def solve(self):
        n = int(input())
        h = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]

        # h = [(h[i], i) for i in range(n)]
        # h.sort()

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

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

        dp = [0] * (n + 1)
        for i, he in enumerate(h):
            update(he, get(he - 1) + a[i])

        # print(dp)
        print(max(dp))

solver = QFlowers()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #最大値
    return max(l, r)
  def set(self, L):
    for i in range(len(L)):
      self.update(i, L[i])
  def update(self, x, v):
    k = x + self.N - 1
    self.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] = self.do(self.T[2*k+1], self.T[2*k+2])
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

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

D = segTree(N)
x = copy.deepcopy(h)
x.sort()
R = {}
for i in range(N):
  R[x[i]] = i

DP = [0] * N
for i in range(N):
  DP[i] = D.getV(0, R[h[i]]) + a[i]
  D.update(R[h[i]], DP[i])

print(max(DP))

Submission status: Accepted

Solution code:
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 += self.tree[m]
                res = max(res,self.tree[m])
                m += 1
            m >>= 1
            if n & 1 ==0:
                #res += self.tree[n]
                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))

Submission status: Accepted

Solution code:
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の値を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): #[A,B)の値, 呼ぶときはquery(a,b)
        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): #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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)
MOD=10**9+7

class Bit:
    def __init__(self, n):
        self.size = n
#        self.node = [0] * (n + 1)
        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
#        self.node[i] += x
        while i <= self.size:
            self.tree[i] = max(self.tree[i],x)
            i += i & -i

#    def get(self,i)
#        return self.node(i+1)

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

#print(modosu)
#print(zaatu)

dp = Bit(n)
for i in range(1,n+1):
#    print(i,zaatu[i])
    dp.add(zaatu[H[i-1]], dp.sum(zaatu[H[i-1]])+A[i-1])

print(dp.sum(n-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
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))


# region fastio

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    # Update ak as x
    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])

    # Min value in [l, r)
    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])

Submission status: Accepted

Solution code:
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):
    #i番目の花を残さないとき
    res1 = st.get_max(0, n+1) 
    #i番目の花を残すとき
    res2 = st.get_max(0, h[i]) + a[i]
    
    dp[i+1] = max(res1, res2)
    st.update(h[i], res2)
print(dp[n])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))