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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    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:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max


#dp[i] : 最後の花の高さがiの時の最大値

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

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):  # 1-indexed
        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):  # i > 0
        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)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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]
    #ans[idx]=new_value
    seg.update(idx,new_value)
mx=seg.query(0,n-1)
print(mx)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

#solve
def solve():
    n = II()
    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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

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

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

#n番目をxに変更して更新する
def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=max(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

#区間[L,R]における最大値を返す(非負整数)
def seg_tree_find_max(L,R):
    L,R=2**m-1+L,2**m-1+R
    qqq=0
    while L<R:
        if L%2==0:
            qqq=max(qqq,tree[L])
        if R%2==1:
            qqq=max(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=max(qqq,tree[L])
    return qqq
  
N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))

m=0
while pow(2,m)<N+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    M=seg_tree_find_max(0,h[i])
    if tree[2**m-1+h[i]]<a[i]+M:
        seg_tree_update(h[i],a[i]+M)

ans=0
for i in range(N+1):
    ans=max(ans,tree[2**m-1+i])

print(ans)

Submission status: Accepted

Solution code:
def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=max(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

def seg_tree_find_max(L,R):
    L,R=2**m-1+L,2**m-1+R
    qqq=0
    while L<R:
        if L%2==0:
            qqq=max(qqq,tree[L])
        if R%2==1:
            qqq=max(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=max(qqq,tree[L])
    return qqq

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

m=0
while pow(2,m)<N+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    M=seg_tree_find_max(0,h[i])
    if tree[2**m-1+h[i]]<a[i]+M:
        seg_tree_update(h[i],a[i]+M)

ans=0
for i in range(N+1):
    ans=max(ans,tree[2**m-1+i])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        #####単位元######
        self.ide_ele = element
        self.size = size

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

        #####segfunc######
        self.segfunc = func

    def apply(self, apply_seq):
        #set_val
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        #built
        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()))
st = Segment_Tree(n+1,max,0)
dp = [0] * (n+1)
for i in range(n):
  hi = H[i]; ai = A[i]
  st.update(hi,st.query(0,hi+1)+ai)
print(st.query(0,n+1))

Submission status: Accepted

Solution code:
import sys

class segTree():
    def __init__(self, N, value):
        d, k = 1, 0
        while d < N:
            d *= 2
            k += 1
        self.tree = [value for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a):
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos):
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    H = [int(h) for h in input().split()]
    A = [int(a) for a in input().split()]
    highest = max(H) + 1
    ans = segTree(highest, 0)
    for i, h in enumerate(H): 
        maxSum = ans.search(0, h, 0, ans.size, 0)
        ans.update(h, A[i] + maxSum)
    print(ans.search(0, highest, 0, ans.size, 0))

    return 0

if __name__ == "__main__":
    solve()