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:
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={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    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
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
## Segment Tree ##

## Test case: ABC 146 F
## https://atcoder.jp/contests/abc146/tasks/abc146_f

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

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
        #set_val
        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
        #build
        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
            
            ## Remove if index is not needed
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
            ## Remove if index is not needed
        
    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))

Submission status: Accepted

Solution code:
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={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    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
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
## Segment Tree ##

## Test case: ABC 146 F
## https://atcoder.jp/contests/abc146/tasks/abc146_f

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

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
        #set_val
        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
        #build
        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
            
            ## Remove if index is not needed
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
            ## Remove if index is not needed
        
    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))

Submission status: Accepted

Solution code:
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()  # ignore trailing spaces


class SegmentTreeRMQ(object):  # 1-indexed [l,r)
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        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
        # print(self.array)

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

Submission status: Accepted

Solution code:
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
 
        # size 以上である最小の 2 冪を size とする
        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)
        # l=0, r=0 の時Noneを返す仕様
        if maxV == None:
            maxV = 0
        seg.set(idx, maxV+a)
 
    ans = seg.get(0, N)
    print(ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


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


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

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

    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():
    # parse input
    N = int(input())
    HS = list(map(int, input().split()))
    VS = list(map(int, input().split()))
    print(solve(N, HS, VS))


# tests
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
    """
# add tests above


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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

# h = [(item, i) for i,item in enumerate(h)]
# h.sort()

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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) 
    # for i in range(n): 
    #     updatebit(BITTree, n, i, arr[i])
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:



def update(tree, index, value):
    while index < len(tree):
        tree[index] = max(tree[index], value)
        index += index & -index


def read(tree, index):
    value = 0
    while index > 0:
        value = max(value, tree[index])
        index -= index & -index
    return value


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    h = read_ints()
    a = read_ints()
    tree = [0]*(N+1)
    max_beauty = 0
    for i in range(N):
        beauty = read(tree, h[i])+a[i]
        update(tree, h[i], beauty)
        max_beauty = max(max_beauty, beauty)
    return max_beauty


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
    def max(self, i):
        s = 0
        while i > 0:
            if s < self.tree[i]:
                s = self.tree[i]
            i -= i & -i
        return s
    def __setitem__(self, i, x):
        while i <= self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i


N, *HA = map(int, open(0).read().split())
H, A = HA[:N], HA[N:]

dp = RMQ(N)
for h, a in zip(H, A):
    dp[h] = a + dp.max(h)

print(dp.max(N))

Submission status: Accepted

Solution code:
class RMQ:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
    def sum(self, i):
        s = 0
        while i > 0:
            if s < self.tree[i]:
                s = self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i


N, *HA = map(int, open(0).read().split())
H, A = HA[:N], HA[N:]

dp = RMQ(N)
for h, a in zip(H, A):
    dp.add(h, a + dp.sum(h))

print(dp.sum(N))