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, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    RMQ = SegmentTree([0] * N, merge_func=max, default=0)
    for i in range(N):
        maximum = RMQ.query(0, H[i]-1)
        RMQ.update(H[i]-1, maximum + A[i])
    print(RMQ.query(0, N))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f4(n, h, a):
    bit = [0] * (n + 1)

    def getmax(h):
        x = h - 1
        m = 0
        while x != 0:
            if m < bit[x]:
                m = bit[x]
            x -= x & -x
        return(m)

    def update(h, v):
        x = h
        while x <= n:
            if bit[x] < v:
                bit[x] = v
            x += x & -x

    for i in range(1, n + 1):
        m = getmax(h[i])
        update(h[i], m + a[i])
    return(max(bit))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))

print(f4(n, h, a))

Submission status: Accepted

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

class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.A[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)>>1
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b):
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1
            r>>=1
        return res

def f(a,b):
    return max(a,b)

n=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))
seg=SegmentTree(n+1,0,f)
for h,a in zip(H,A):
    t=seg.query(0,h)
    seg.update(h,a+t)
print(seg.get_top())

Submission status: Accepted

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

class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        i=1
        while 2**i<n:
            i+=1
        self.d=default
        self.leaf=2**i
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.A[i+self.leaf-1]
    def update(self,idx,a):
        idx+=self.leaf-1
        self.tree[idx]=a
        while idx:
            idx=(idx-1)//2
            self.tree[idx]=self.merge(self.tree[idx*2+1],self.tree[idx*2+2])
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b): #[a,b)
        T=self.tree
        l=a+self.leaf-1
        r=b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1
            r>>=1
        return res

def f(a,b):
    return max(a,b)

n=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))
seg=SegmentTree(n+1,0,f)
for h,a in zip(H,A):
    t=seg.query(0,h)
    seg.update(h,a+t)
print(seg.get_top())

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

h = [0] + h
a = [0] + a

bit = [0] * (n+1)
def update(a, w):
    x = a
    while x <= n:
        bit[x] = max(bit[x], w)
        x += x & -x

def solve(a):
    res = 0
    x = a
    while x > 0:
        res = max(res, bit[x])
        x -= x & -x
    return res

for i in range(1, n+1):
    ma = solve(h[i]-1)
    update(h[i], ma + a[i])

print(max(bit))

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

h = [0] + h
a = [0] + a

dp = [0] * (n+1)

bit = [0] * (n+1)
def update(a, w):
    x = a
    while x <= n:
        bit[x] = max(bit[x], w)
        x += x & -x

def solve(a):
    res = 0
    x = a
    while x > 0:
        res = max(res, bit[x])
        x -= x & -x
    return res

for i in range(1, n+1):
    ma = solve(h[i]-1)
    update(h[i], ma + a[i])

print(max(bit))

Submission status: Accepted

Solution code:


class FenwickTree:
    def __init__(self, size):
        self.elems = [0 for _ in range(size)]
        self.size = len(self.elems)

    def query(self, ind):
        resp = 0
        while ind > 0:
            resp = max(resp, self.elems[ind])
            ind -= ind & -ind
        return resp

    def update(self, ind, val):
        while ind < self.size:
            self.elems[ind] = max(self.elems[ind], val)
            ind += ind & -ind


n = input()
h = map(int, raw_input().split())
a = map(int, raw_input().split())
tree = FenwickTree(n + 1)

dp = [0] * n
for i in range(n):
    dp[i] = a[i] + tree.query(h[i])
    tree.update(h[i], dp[i])
print(max(dp))

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
# ---------------------------------------------------------------------------------
from collections import deque
N0 = 2**(N).bit_length()
INF = float("inf")
INF = -(2**31-1) 

data = [INF]*(2*N0)

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

# $B6h4V(B[l, r)$B$N:G>.CM(B
def query(l,r):
    L = l + N0 - 1 # $B$J$s$G(BN0$B$rB-$7$F$$$k!D(B?
    R = r + N0 - 1
    # print("L: {}, R: {}".format(L,R))
    s = INF
    while L < R:
        # print("\tL: {}, R: {}".format(L,R))

        if R & 1 == 0:
            s = max(s, data[R])
            R -= 2
            # R -= 1
            # s = max(s,data[R-1])
        else:
            s = max(s, data[R])
            R -= 3

        if L & 1:
            # s = max(s, data[L-1])
            s = max(s, data[L])
            # L += 1
            L -= 1
        else:
            s = max(s,data[L])
            
        L >>= 1; R >>= 1
    if L == R:
        s = max(s,data[L])
    return s
# def query(l,r):
#     L = l + N0 # $B$J$s$G(BN0$B$rB-$7$F$$$k!D(B?
#     R = r + N0
#     print("L: {}, R: {}".format(L,R))
#     s = INF
#     while L < R:
#         print("\tL: {}, R: {}".format(L,R))
# 
#         if R & 1:
#             R -= 1
#             s = max(s,data[R-1])
#         if L & 1:
#             s = max(s, data[L-1])
#             L += 1
#         L >>= 1; R >>= 1
#     return s
# ---------------------------------------------------------------------------------
dp = [0] * (N+1)
#dp = [ [0] * (N+1) for _ in range(2*10**5+1)]

for i in range(1,N+1):
    # print("query: 0 to H[i-1]=",H[i-1])
    dp[i] = max(query(0, H[i-1]), 0) + A[i-1]
    update(H[i-1], dp[i])
print(max(dp))

Submission status: Accepted

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

class SegTreeMax:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [0]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = max(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = max(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.nodes[k]
        return max(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

segt = SegTreeMax([0]*N)
ans = 0
for h,a in zip(H,A):
    v = segt.query(0,h) + a
    segt.update(h-1,v)
    ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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


#Segment tree（区間の最大値を求めるバージョン）
for i in range(30):#要素数以上の2のベキを見つける
    if N<=2**i:
        seg_el=2**i#Segment treeの台の要素数
        break

SEG=[0]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    while i>=0:
        SEG[i]=max(x,SEG[i])
        i=(i-1)//2

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,infを出力
        return -float("inf")
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return max(vl,vr)

for i in range(N):
    h,a=H[i],A[i]
    x=getvalues(0,h,0,0,seg_el)
    update(h-1,x+a,seg_el)

print(getvalues(0,N,0,0,seg_el))

Submission status: Accepted

Solution code:
def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))

Submission status: Accepted

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

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
ans = 0
update(0, 0)
for i in I:
    v = query(0, i+1) + A[i]
    ans = max(ans, v)
    update(i+1, v)
print(ans)

Submission status: Accepted

Solution code:
class Segmenttree_max():
    def __init__(self, number):
        n = 1
        while n < number:
            n *= 2
        self.n = n
        self.list = [0] * (2 * n - 1)

    def add(self, i, x):  # 0indexed ith add x
        i += self.n - 1
        self.list[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.list[i] = max(self.list[2 * i + 1], self.list[2 * i + 2])

    def search(self, a, b, k, l, r):  # call as search(a,b,0,0,self.n) maximum in [a,b)
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.list[k]
        else:
            vl = self.search(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self.search(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)


N = int(input())
H = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
tree = Segmenttree_max(N)
dp = [0] * (N + 1)
for i in range(1, N + 1):
    dp[i] = tree.search(0, H[i - 1] - 1, 0, 0, tree.n) + A[i - 1]
    tree.add(H[i - 1] - 1, dp[i])
ans=0
for i in range(N+1):
    ans=max(ans,dp[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
h = list(map(int,input().split()))
a = list(map(int,input().split()))
dp = [0] * (n+1)
# N: 処理する区間の長さ
N0 = 2**(n).bit_length()
INF = -(2**31-1)
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(1,n+1):
  dp[i] = max(query(0,h[i-1]),0) + a[i-1]
  update(h[i-1], dp[i])
print(max(dp))

Submission status: Runtime Error

Solution code:
class BITmax:
    def __init__(self, N, init=0):
        self.init = init
        self.tree = [self.init] * (N+1)
    
    def set(self, x, value):
        while x < N + 1:
            old = self.tree[x]
            if value <= old:
                break
            self.tree[x] = value
            x += x & -x
    
    def find_max_to(self, x):
        result = self.init
        while x > 0:
            result = max(result, self.tree[x])
            x -= x & -x
        return result

def main():
    N = int(input())
    dpt = BITmax(N)

    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))

    for h, b in zip(h_list, b_list):
        dpt.set(h, dpt.find_max_to(h-1) + b)

    print(max(dpt.tree))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
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(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in 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: Runtime Error

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(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in 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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(2*n-1)
    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(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in 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(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
li=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
ans=0
def findans(tot,j,height):
    global ans
    if j==n:
        ans=max(ans,tot)
        return
    if li[j]>height:
        findans(tot+co[j],j+1,li[j])
    findans(tot,j+1,height)
findans(0,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = 0
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = temp.left.val + temp.right.val
    return temp
 
def update(root,start,va):
    if root.start==root.end==start:
        root.val = va
    elif root.start<=start and root.end>=start:

        root.left=update(root.left,start,va)
        root.right=update(root.right,start,va)
        root.val = max(root.left.val,root.right.val)
    return root
    
def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return 0
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

root = build([],0,200005)
n = val()
h = li()
a = li()
ans = 0

for i in range(n):
    curr = query(root,-1,h[i])
    temp = curr + a[i]
    ans = max(ans,temp)
    root = update(root,h[i],temp)
print(ans)from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = 0
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = temp.left.val + temp.right.val
    return temp
 
def update(root,start,va):
    if root.start==root.end==start:
        root.val = va
    elif root.start<=start and root.end>=start:

        root.left=update(root.left,start,va)
        root.right=update(root.right,start,va)
        root.val = max(root.left.val,root.right.val)
    return root
    
def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return 0
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

root = build([],0,200005)
n = val()
h = li()
a = li()
ans = 0

for i in range(n):
    curr = query(root,-1,h[i])
    temp = curr + a[i]
    ans = max(ans,temp)
    root = update(root,h[i],temp)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
INF=10**9
d=[[INF]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for i in range(m):
    a,b=map(int,input().split())
    d[a-1][b-1]=1
    d[b-1][a-1]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in d:
    print(i.count(2))

Submission status: Runtime Error

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

import math

num = 2**(int(math.log2(N+1))+1)
seg = [0]*(2*num-1)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -float("inf")
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


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

print(max(seg))

Submission status: Runtime Error

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 += 1
    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: Runtime Error

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

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+1)]
print(max(new_arr[1::]))
print(new_arr)
for seq in new_arr:
    idx=seq[2]
    ans[idx]=max(ans[idx::])+seq[1]
print(max(ans))

Submission status: Runtime Error

Solution code:

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 = 131072
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 = 0, l = 0, r = n):
    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) + 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 (max(dp))

Submission status: Runtime Error

Solution code:

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 = 131073
data = [0] * n
# 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 = 0, l = 0, r = n):
    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) + 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 (max(dp))

Submission status: Runtime Error

Solution code:

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

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

def update(k, a):
    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 = 0, l = 0, r = n):
    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], A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(1, H[i]) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i], dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (max(dp))