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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
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)
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
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: Time Limit Exceeded

Solution code:

def flower(n,arr_h,arr_b):
	b=1
	while b<n:
		b*=2
	seg_t=[0]*2*b

	def query(x):
		l=0+b
		r=x+b
		ans=0
		while l<=r:
			if l%2==1:
				ans=max(ans,seg_t[l])
				l+=1
			if r%2==0:
				ans=max(ans,seg_t[r])
				r-=1
			l//=2
			r//=2
		return ans

	def update(ind,val):
		ind+=b
		while ind>0:
			# print(b,ind)
			seg_t[ind]=max(seg_t[ind],val)
			ind//=2

	ans=0
	for ind in range(n):
		h=arr_h[ind]
		bu=arr_b[ind]

		k=query(h)
		ans=max(ans,k+bu)
		update(h,k+bu)
		# print(ind,h,k,seg_t)
	return ans

# 4
# 3 1 4 2
# 10 20 30 40


n=int(input())
arr_h=list(map(lambda x:int(x)-1,input().split()))
arr_b=list(map(int,input().split()))
# res=independent_set(n,graph)

res=flower(n,arr_h,arr_b)

# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lg=input().split()
lh=[int(i) for i in lg]
lb=input().split()
lbi=[int(i) for i in lb]
dp=[0 for i in range(n)]
dp[0]=lbi[0]
for i in range(1,n):
    maxa=[]
    for j in range(i):
        if(lh[j]<lh[i]):
            maxa.append(dp[j])
    if(maxa==[]):
        dp[i]=lbi[i]
        continue
    dp[i]=max(maxa)+lbi[i]
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
H=tuple(map(int,input().split()))
A=tuple(map(int,input().split()))
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
        self.d=[0]*N
    def update(self,i,x):
        self.d[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        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
s=SegTreeMax(N+1)
s.update(0,0)
for i,h in enumerate(H):
    m=s.max(0,h)
    s.update(h,m+A[i])
print(s.max(0,N+1))

Submission status: Time Limit Exceeded

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

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SEGMENT_TREE:
    def __init__(self, N):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.tree = [0] * (2 * N)  # 問題により修正

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = max(
                self.tree[i * 2], self.tree[i * 2 + 1])  # 問題により修正

    def update(self, p, value):
        """配列arr[p]をvalueに変更"""
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = max(self.tree[i], self.tree[i ^ 1])  # 問題により修正
            i //= 2

    def query(self, l, r):
        """
        l, r: 0-indexed
        半開区間[l, r)から条件を満たす数を返す
        """
        N = self.N
        res = 0  # 問題により修正
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = max(res, self.tree[l])
                l += 1
            if (r & 1):
                r -= 1
                res = max(res, self.tree[r])
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N + 1)
    for h, a in zip(H, A):
        left = seg.query(0, h + 1)
        seg.update(h, left + a)
    print(seg.query(0, N+1))

Submission status: Time Limit Exceeded

Solution code:
class SEGMENT_TREE:
    def __init__(self, N):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.tree = [0] * (2 * N)  # 問題により修正

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = max(
                self.tree[i * 2], self.tree[i * 2 + 1])  # 問題により修正

    def update(self, p, value):
        """配列arr[p]をvalueに変更"""
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = max(self.tree[i], self.tree[i ^ 1])  # 問題により修正
            i //= 2

    def query(self, l, r):
        """
        l, r: 0-indexed
        半開区間[l, r)から条件を満たす数を返す
        """
        N = self.N
        res = 0  # 問題により修正
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = max(res, self.tree[l])
                l += 1
            if (r & 1):
                r -= 1
                res = max(res, self.tree[r])
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N + 1)
    for h, a in zip(H, A):
        left = seg.query(0, h + 1)
        seg.update(h, left + a)
    print(seg.query(0, N+1))

Submission status: Time Limit Exceeded

Solution code:

import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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 = int(input().rstrip())
h = [int(i) for i in input().rstrip().split()]
a = [int(i) for i in input().rstrip().split()]
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: Time Limit Exceeded

Solution code:

import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



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 = int(input().rstrip())
h = [int(i) for i in input().rstrip().split()]
a = [int(i) for i in input().rstrip().split()]
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: Time Limit Exceeded

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,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# 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().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]



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: Time Limit Exceeded

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,0,h[i])
    temp = curr + a[i]
    ans = max(ans,temp)
    root = update(root,h[i],temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
hs = list(map(int, input().split()))
ns = list(map(int, input().split()))

dp = [[0] * (n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1, n + 1):
        if hs[i - 1] == j:
            dp[i][j] = max(dp[i - 1][k] for k in range(0, j)) + ns[i - 1]
        else:
            dp[i][j] = dp[i - 1][j]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i):
  if i==n:
    return 0
  if z[i]==-1:
    z[i]=b[i]
    for j in xrange(i+1,n):
      if a[i]<a[j]:
        z[i]=max(z[i],b[i]+f(j))
  return z[i]
n=input()
a=map(int,raw_input().split())
b=map(int,raw_input().split())
z=[-1]*n
print max(f(i) for i in xrange(n))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, A, n=18, inf=10**20):
        l = len(A)
        self.size = n
        self.array = [inf]*(2**(n+1)-1)
        for i in range(l):
            self.array[i+2**n-1] = A[i]
        for i in range(2**n-2, -1, -1):
            self.array[i] = max(self.array[2*i+1], self.array[2*i+2])

    def _subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return 0
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_max = self._subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_max = self._subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return max(l_max, r_max)

    def max(self, l, r):
        return self._subquery(l, r, 0, 0, 2**self.size)

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = c
        while tmp > 0:
            tmp = (tmp - 1) // 2
            l = self.array[2 * tmp + 1]
            r = self.array[2 * tmp + 2]
            self.array[tmp] = max(l, r)

n = int(input())
*H, = map(lambda x: int(x)-1, input().split())
*A, = map(int, input().split())
DP = SegmentTree([0]*n)
for i in range(n):
    tmp = DP.max(0, H[i])
    DP.update(H[i], tmp+A[i])
print(DP.max(0, n))

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]=(i番目まで使って最後の高さがjであるようなものの美しさの最大値)
# dp[i][j]=max(dp[i-1][k])+a[i](h[i]==j,0<=k<j),dp[i-1][j](otherwise)

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


N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
n=N+1
#####単位元######
ide_ele = 0 #変える
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
dp=[0]*n
init(dp)
for i in range(N):
    # dp[h[i]]の値をdp[k](kは[0,h[i]))の最大値+a[i]にする
    # 手で書いてみると動きがわかりやすい
    update(h[i],query(0,h[i])+a[i])
print(query(0,n))

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  copy import deepcopy
from bisect import bisect_left

class SegmentTree():

    def __init__(self,init_val,func,unit): #init_valは長さnの配列 O(2*n)
        n = len(init_val)
        self.unit = unit #unitは単位元
        self.size = pow(2,n - 1).bit_length() #n以上の最小の2のべき乗
        self.seg = [self.unit] * (2 * self.size) #セグメントツリー本体
        self.f = func #セグ木により異なる関数
        
        for i in range(n):
            self.seg[i + self.size - 1] = init_val[i] 
        
        for i in range(self.size - 2,-1,-1):
            self.seg[i] = self.f(self.seg[2 * i + 1],self.seg[2 * i + 2])
    
    def update(self,k,x): #k番目の要素をxに変更する O(logN)
        k += self.size - 1
        self.seg[k] = x
        while k:
            k = (k - 1)//2
            self.seg[k] = self.f(self.seg[2 * k + 1],self.seg[2 * k + 2])
    
    def query(self,p,q): #[p,q)のクエリに答える　半開区間であることに注意 O(logN)
        if q <= p:
            return self.unit

        p += self.size - 1 
        q += self.size - 2
        res = self.unit

        while q - p > 1:

            if (p&1) == 0:
                res = self.f(res,self.seg[p])

            if (q&1) == 1:
                res = self.f(res,self.seg[q])
                q -= 1

            p //= 2
            q = (q - 1)//2
        
        if p == q:
            res = self.f(res,self.seg[p])
        else:
            res = self.f(self.f(res,self.seg[p]),self.seg[q])
        
        return res


def main():
    n = int(input())
    H = list(map(int,input().split()))
    A = list(map(int,input().split()))
    
    dp = SegmentTree([0] * (n + 1),max,0)
    ans = 0
    for i in range(n):
        before_beaty = dp.query(0,H[i])
        if dp.query(H[i],H[i] + 1) < A[i] + before_beaty:
            dp.update(H[i],before_beaty + A[i])
            ans = max(ans,before_beaty + A[i])
    
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def base10to(n, b):
    if b <= n:
        return base10to(n//b, b) + str(n%b)
    return str(n%b)

num = 2**(len(base10to(N+1,2))+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 -1
    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(query(0,N+2,0,0,num))

Submission status: Time Limit Exceeded

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

def base10to(n, b):
    if b <= n:
        return base10to(n//b, b) + str(n%b)
    return str(n%b)

num = 2**(len(base10to(N+1,2))+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: Time Limit Exceeded

Solution code:
class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[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()))
dp = [0] * N
S = SegmentTree(dp)
for i in range(N):
    tmp = S.query(0,h[i]-1)
    S.update(h[i]-1, tmp+a[i])
print(S.query(0,N))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get_0(self, index):
        s = self.one
        j = index // self.k

        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def get(self, index1, index2):
        s = self.one
        j1 = index1 // self.k
        j2 = index2 // self.k

        if j1 == j2:
            s = self.one
            for i in range(index1, index2 + 1):
                s = self.func(s, self.a[i])
            return s

        for i in range(index1, j1 * self.k + self.k):
            s = self.func(s, self.a[i])
        for i in range(j1+1, j2):
            s = self.func(s, self.b[i])
        for i in range(j2 * self.k, index2 + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(0, h[i])
    buc.update(h[i], j + a[i])

print(buc.get(0, n))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), 400)

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))