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:
def solve():
    import sys

    input = sys.stdin.readline

    # usage: update, query = SegmentTreeClosure(init_val=dp, segfunc=max, ide_ele=0)
    # 再帰なしsegment tree
    # https://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/
    # class版original: @solzard_
    def SegmentTreeClosure(init_val, segfunc, ide_ele) -> 'update,query':
        size = 1 << (len(init_val) - 1).bit_length()

        # _build
        tree = [ide_ele] * (size * 2 - 1)
        for idx, val in enumerate(init_val, size - 1):  # set
            # modify val if needed (e.g. str -> ord())
            tree[idx] = val
        for idx in range(size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        # closure_1
        def update(idx: int, val) -> None:
            nonlocal size
            nonlocal tree
            nonlocal segfunc

            idx += size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        # closure_2
        def query(left: int, right: int) -> 'result':
            nonlocal size
            nonlocal tree
            nonlocal segfunc

            left += size
            right += size
            ret = ide_ele  # left >= right: return ide_ele
            while left < right:  # どの段も奇偶...順
                if left % 2:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right % 2:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left //= 2
                right //= 2

            return ret

        return update, query

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))

    dp = [0] * (n + 1)
    # dp[j] := 末尾jの単調増加列の美しさの総和の最大値

    update, query = SegmentTreeClosure(init_val=dp, segfunc=max, ide_ele=0)
    for h_, a_ in zip(h, a):
        # i本目を取って末尾にするとき
        max_ = query(0, h_) + a_
        update(h_, max_)
    print(query(0, n + 1))


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
    # 高さに対する美しさの最大値なので、高さ[0,n]の(n+1)要素に対して、segを考える
    seg = [0] * (size * 2 - 1)

    def update(seg, k, x):
        k += size - 1
        seg[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(seg, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        # 区間が重ならない

        if a <= l and r <= b:
            return seg[k]
        # 完全被覆

        m = (l + r) // 2
        vl = get(seg, a, b, k * 2 + 1, l, m)
        vr = get(seg, a, b, k * 2 + 2, m, r)
        return max(vl, vr)
        # 部分被覆

    for h_, a_ in zip(h, a):
        update(seg, h_, get(seg, 0, h_) + a_)
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return get(seg, 0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035

Submission status: Time Limit Exceeded

Solution code:
def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
    seg = [0] * (size * 2 - 1)

    def update(k, x):
        k += size - 1
        seg[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        # 区間が重ならない

        if a <= l and r <= b:
            return seg[k]
        # 完全被覆

        m = (l + r) // 2
        vl = get(a, b, k * 2 + 1, l, m)
        vr = get(a, b, k * 2 + 2, m, r)
        return max(vl, vr)
        # 部分被覆

    for h_, a_ in zip(h, a):
        tmp = get(0, h_)
        update(h_, tmp + a_)
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().rstrip().split()))
    a = tuple(map(int, input().rstrip().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035

Submission status: Time Limit Exceeded

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

def main():
  N = int(input())
  H = tuple(map(int,input().split()))
  A = tuple(map(int,input().split()))
  
  dp = [0 for _ in range(N)]
  
  for i in range(N):
    for j in range(H[i]-1,N):
      if j == H[i]-1:
        dp[j] += A[i]
        cur = dp[j]
      else:
        if dp[j] < cur:
          dp[j] = cur
        else:
          break
  #print(dp)
  dp.sort()
  print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
N = I()
h = LI()
a = LI()
dp = [0] * (N+1)
ans = int(0)

dp[h[0]] = a[0]
for i in range(N-1):
    dp[h[i+1]] = max(dp[:h[i+1]]) + a[i+1]

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
h = [int(x) - 1 for x in input().split()]
a = [int(x) for x in input().split()]

l2N = 0
n = N
while n > 1:
    n = -(-n//2)
    l2N += 1
N = 2**l2N

seg = [0] * (2 * 2**l2N - 1)

def update(H, x):
    H += 2**l2N - 1
    seg[H] = x
    while H > 0:
        H = (H - 1) // 2
        seg[H] = max(seg[H*2+1], seg[H*2+2])

def maxSrch(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = maxSrch(a, b, k*2+1, l, (l+r)//2)
        vr = maxSrch(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

for H,A in zip(h,a):
    update(H, maxSrch(0,H,0,0,N) + A)
print(seg[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
h = [int(x) - 1 for x in input().split()]
a = [int(x) for x in input().split()]

dp = [0] * N
for i,j in zip(h,a):
    if i == 0:
        dp[i] = j
    else:
        dp[i] = max(dp[0:i]) + j
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0]*n
dp[0] = bs[0]

for i in range(1,n):
    thisH = hs[i]
    thisB = bs[i]
    maxB = thisB
    for j in range(0,i):
        if hs[j]<thisH:
            totalB = dp[j]+thisB
            if totalB > maxB:
                maxB = totalB
    dp[i] = maxB

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=[0]*(n+1)
t=np.zeros(n+1)
h=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    s[h[i]]=t[h[i]]+a[i]
    t[h[i]:]=np.maximum(t[h[i]:],s[h[i]])
print(int(t[-1]))

Submission status: Time Limit Exceeded

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

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

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

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

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

class Segment_Tree:
    def __init__(self, seq, _INF = -INF):
        self.seq, self.N, N = seq, 1, len(seq)
        while self.N < N:
            self.N *= 2
        self.data = [_INF for i in range(self.N*2-1)]
        for k in range(N):
            self.Update(k, seq[k])
    def Update(self, k, a):
        self.seq[k] = a
        k += self.N-1
        self.data[k] = a
        while k > 0:
            k = (k-1)//2
            self.data[k] = max(self.data[k*2+1], self.data[k*2+2])
    def RMQ(self, a, b):
        def subRMQ(a, b, k, l, r):
            if r <= a or b <= l:
                return -INF
            if a <= l and r <= b:
                return self.data[k]
            else:
                vl = subRMQ(a, b, k*2+1, l, (l+r)//2)
                vr = subRMQ(a, b, k*2+2, (l+r)//2, r)
                return max(vl, vr)
        return subRMQ(a, b, 0, 0, self.N)

N = int(input())
H = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
dp = Segment_Tree([0]*(N+1))
for h, a in zip(H, A):
    dp.Update(h, dp.RMQ(0, h)+a)
print(dp.RMQ(0, N+1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

H = [int(j) for j in input().split()]
B = [int(j) for j in input().split()]
maxH = max(H)
dp = [0 for i in range(maxH + 1)]

base = 1
while base <= n:
    base *= 2

tree = [0 for i in range(2 * base)]

for i in range(n):
    h = H[i]
    b = B[i]

    l = base
    r = base + h
    best = 0

    while l <= r:
        if (l & 1) == 1:
            best = max(best, tree[l])
            l += 1
        if (r & 1) == 0:
            best = max(best, tree[r])
            r -= 1
        l //= 2
        r //= 2

    dp[h] = best + b
    tree[h + base] = best + b

    index = (h + base) // 2
    while index >= 1:
        tree[index] = max(tree[2 * index], tree[2 * index + 1])
        index //= 2

print(max(dp))

Submission status: Time Limit Exceeded

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

MOD = 1e9+7

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

s = sum(a)

def solve(i, prev):
    if (i==n):
        return 0

    if prev!=-1 and h[prev]>h[i]:
        #pluck
        return a[i]+solve(i+1, prev)
    else:
        #choice
        return min(a[i]+solve(i+1, prev), solve(i+1, i))

print(s-solve(0, -1))

Submission status: Time Limit Exceeded

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

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

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

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

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

    return t
    

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

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

    print(max(t))


main()

Submission status: Time Limit Exceeded

Solution code:
# @author 

import sys

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

        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = a[i - 1]
            for j in range(i):
                if h[i - 1] > h[j - 1]:
                    dp[i] = max(dp[i], dp[j] + a[i - 1])

        # print(dp)
        print(dp[-1])

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

solver.solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return -1
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * N

for i in range(N):
	tmp = 0
	for j in range(h[i] - 1):
		if dp[j] > tmp:
			tmp = dp[j]
			
	dp[h[i] - 1] = a[i] + tmp
		
print(max(dp))

Submission status: Time Limit Exceeded

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

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

N += 1

# N: 処理する区間の長さ
N0 = 2**(N-1).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

update(0,0)

for h,a in zip(H,A):
    update(h,query(0,h) + a)

ans = query(0,N+1)
print(ans)

Submission status: Time Limit Exceeded

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

value = [0] * (max(h) + 1)

for i in range(N):
  value[h[i]] = a[i] + max(value[:h[i]])
  
print(max(value))

Submission status: Time Limit Exceeded

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

value = [0] * (max(h) + 1)

for i in range(N):
  value[h[i]] = a[i] + max(value[:h[i]])
  
print(max(value))

Submission status: Time Limit Exceeded

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

value = [0] * (max(H) + 1)

for h, a in zip(H, A):
  value[h] = a + max(value[:h])
  
print(max(value))

Submission status: Time Limit Exceeded

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

value = [0] * (max(H) + 1)

for i, h in enumerate(H):
  value[h] = max(a[i] + max(value[:h]), value[h])
  
print(max(value))

Submission status: Time Limit Exceeded

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

value = [0] * (max(H) + 1)

for h, a in zip(H, A):
  value[h] = max(a + max(value[:h]), value[h])
  
print(max(value))

Submission status: Time Limit Exceeded

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

value = [0] * (max(H) + 1)

for h, a in zip(H, A):
  if h == 1:
    value[h] = max(value[h], a)
  else:
    value[h] = max(a + max(value[:h]), value[h])
  
print(max(value))

Submission status: Time Limit Exceeded

Solution code:
def f(n, hs, a_s):
    sum_a = [0] * n
    sum_a[0] = a_s[0]
    for ai, a in enumerate(a_s[1:]):
        mx = 0
        h = hs[ai + 1]
        for i in range(ai + 1):
            if h > hs[i]:
                if sum_a[i] > mx:
                    mx = sum_a[i]
        sum_a[ai + 1] = a + mx
    return sum_a[-1]


n = int(input())
hs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
print(f(n, hs, a_s))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
hs=list(map(int, input().split()))
a_s=list(map(int, input().split()))

sum_a=[0]*n
sum_a[0]=a_s[0]
for ai,a in enumerate(a_s[1:]):
    mx = 0
    h=hs[ai+1]
    for i in range(ai+1):
        if h>hs[i]:
            if sum_a[i]>mx:
                mx=sum_a[i]
    sum_a[ai+1]=a+mx
print(sum_a[-1])

Submission status: Time Limit Exceeded

Solution code:


def build_tree(node,a,b):
    if(a == b):
        tree[node] = arr[a]
        return 
    mid = (a+b)//2
    build_tree(2*node,a,mid)
    build_tree(2*node+1,mid+1,b)
    tree[node] = max(tree[2*node],tree[2*node+1])


def query_tree(node,a,b,i,j):
    if(a>b or a>j or b<i):
        return mina
    if(a>= i and b<=j):
        return tree[node]
    mid = (a+b)//2
    q1 = query_tree(2*node,a,mid,i,j)
    q2 = query_tree(2*node+1,mid+1,b,i,j)
    return max(q1,q2)

def update_tree(node,a,b,i,val):
    if(a>b or a>i or b<i):
        return mina
    if(a==b):
        tree[node] = val
        return 
    mid = (a+b)//2
    update_tree(2*node,a,mid,i,val)
    update_tree(2*node+1,mid+1,b,i,val)
    tree[node] = max(tree[2*node],tree[2*node+1])

mina = -123254346


n = int(input())
tree = [0 for i in range(4*n + 4)]

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

dp = [0 for i in range(n+1)]

for i in range(n):
    dp[h[i]] = a[i]
    if(i>= 1):
        maxa = query_tree(1,0,n-1,0,h[i]-1)
        dp[h[i]] = max(dp[h[i]],maxa+a[i])
    update_tree(1,0,n-1,h[i],dp[h[i]])
    '''for j in range(h[i]):
        #if(h[j] <= h[i]):
        dp[h[i]] = max(dp[h[i]] , dp[j] + a[i])'''

ans = -1
for i in range(n+1):
    ans = max(ans,dp[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        hi = h[i]
        temp = dp[hi - 1] + a[i]
        dp[hi:] = [x if x > temp else temp for x in dp[hi:]]
    return(dp[-1])

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

print(f3(n, h, a))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        hi = h[i]
        temp = dp[hi - 1] + a[i]
        for j in range(hi, n + 1):
            if dp[j] < temp:
                dp[j] = temp
            else:
                break
    return(dp[-1])

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

print(f3(n, h, a))

Submission status: Time Limit Exceeded

Solution code:



n = int(input())
heights = list(map(int,input().split()))
values  = list(map(int,input().split()))
dp = [values[i] for i in range(n)]
for i in range(n):
    for j in range(i-1,-1,-1):
        if(heights[i] >= heights[j]):
            dp[i] = max(dp[i],dp[j] + values[i])

ans = -123
for i in range(n):
    ans = max(ans,dp[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        hi = h[i]
        dp[hi] = max(dp[:hi]) + a[i]
    return(max(dp))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from array import array
import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = array('L', [0] * (n + 1))
    for i in range(1, n + 1):
        m = max(dp[:h[i]])
        dp[h[i]] = m + a[i]
    return(max(dp))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        m = max(dp[:h[i]])
        dp[h[i]] = m + a[i]
    return(max(dp))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        i1 = 2 * i + 1
        i2 = i1 + 1
        lr = (l + r) // 2
        lmax = getmax(a, b, i1, l, lr)
        rmax = getmax(a, b, i2, lr, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        lmax = getmax(a, b, 2 * i + 1, l, (l + r) // 2)
        rmax = getmax(a, b, 2 * i + 2, (l + r) // 2, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, h, a):
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dpi = dp[i]
        dpi1 = dp[i - 1]
        for j in range(1, n + 1):
            dpi[j] = dpi1[j]
            if h[i] <= j:
                dpij_ = dpi1[h[i] - 1] + a[i]
                if dpij_ > dpi[j]:
                    dpi[j] = dpij_
    return(dp[-1][-1])

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())

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

p = [-1, h[0]]
q = [0, a[0]]

for i in range(n):
    t = bisect_left(p, h[i])
    p.insert(t, h[i])
    q.insert(t, max(q[:t]) + a[i])

print(max(q))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

dp = [0] * n

dp[n-1] = a[n-1]

for i in range(n-2, -1, -1):
    temp = 0
    for j in range(i+1, n):
        if h[i] < h[j]:
            temp = max(temp, dp[j])
    dp[i] = temp + a[i]

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
h = tuple(map(lambda x:int(x)-1,input().split()))
a = tuple(map(int,input().split()))

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

#初期化
#num : nより大きい最小の2のべき乗
num = 1
while num <= n:
    num *= 2
seg = [0]*(2*num-1)

#dp[i]:i番目が最後となる時の美しさの最大値
dp = [a[0]] + [0]*(n-1)
update(h[0],a[0])
for i in range(1,n):
    dp[i] = max(0,query(0,h[i],0,0,num))+a[i]
    update(h[i],dp[i])

print(max(dp))

Submission status: Time Limit Exceeded

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
    # oldk = k
    # k += N0-1 # $B$3$N:n6H$O!D!D(B? #$B0lHV2<$NCJ$K(B
    # data[k] = k # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    # data[k] = oldk # $B$3$l@N$NCM$rF~$l$J$$$H$$$1$J$$$s$8$c$J$$$N!)(B
    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 # $B$J$s$G(BN0$B$rB-$7$F$$$k!D(B?
    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
# ---------------------------------------------------------------------------------
dp = [0] * (N+1)
#dp = [ [0] * (N+1) for _ in range(2*10**5+1)]

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

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:2*i+3])

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

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

lis_h = [0]
lis_v = [0]

for h,a in zip(H,A):
    i = bisect(lis_h, h)
    v = lis_v[i-1] + a
    j = bisect(lis_v, v)

    lis_h = lis_h[:i] + [h] + lis_h[j:]
    lis_v = lis_v[:i] + [v] + lis_v[j:]
print(lis_v[-1])

Submission status: Time Limit Exceeded

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