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
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 = init(N)
data = [0] * (2 * MAX_N - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        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
    if a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

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

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

print (ans)

# print (update(1, 1))
# print (update(2, 5))
# print (query(1, 2))

Submission status: Time Limit Exceeded

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

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


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

    #初期化
    N = int(input())
    n = init(N)
    data = [0] * (2 * MAX_N - 1)

    def update(k, a):
        k += n - 1
        data[k] = a
        while k > 0:
            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
        if a <= l and r <= b:
            return data[k]
        else:
            v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
            v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
            return max(v1, v2)

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

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

    print (ans)

    # print (update(1, 1))
    # print (update(2, 5))
    # print (query(1, 2))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    #区間の管理は　[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 = init(N) + 1
    data = [0] * (2 * MAX_N - 1)

    def update(k, a):
        k += n - 1
        data[k] = a
        while k > 0:
            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
        if a <= l and r <= b:
            return data[k]
        else:
            v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
            v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
            return max(v1, v2)

    def initialize(A): #リストAを与えて初期化する
        for i, a in enumerate(A):
            data[i + n - 1] = a
        for i in range(N + n - 1, 0, -2):
            tmp = i
            tmp = (tmp - 1) //2
            data[tmp] = max(data[tmp * 2 + 1], data[tmp * 2 + 2])

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

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

    print (ans)

    # print (update(1, 1))
    # print (update(2, 5))
    # print (query(1, 2))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
MAX_N = 10 ** 6
# MAX_N = 20


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

#初期化
N = int(input())
n = init(N) + 1
data = [0] * (2 * MAX_N - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        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
    if a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = a
    for i in range(N + n - 1, 0, -2):
        tmp = i
        tmp = (tmp - 1) //2
        data[tmp] = max(data[tmp * 2 + 1], data[tmp * 2 + 2])

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

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

print (ans)

# print (update(1, 1))
# print (update(2, 5))
# print (query(1, 2))

Submission status: Time Limit Exceeded

Solution code:
import sys

class segTree(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d = 1
        while d < N: d <<= 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a): #update cell i with value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:


class SegTreeMax():
    def __init__(self, l):
        self.N = 1
        while self.N < len(l):
            self.N *= 2
        self.L = [0 for _ in range(self.N*2-1)]
        for i in range(len(l)):
            self.L[i+self.N-1] = l[i]
        for i in range(self.N-2, -1, -1):
            self.L[i] = max(self.L[i*2+1], self.L[i*2+2])

    def update(self, k, v):
        k += self.N-1
        self.L[k] = v
        while k > 0 and self.L[(k-1)//2] < v:
            k = (k-1)//2
            self.L[k] = v

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

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


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

    S = SegTreeMax([0 for i in range(N)])
    for i in range(N):
        S.update(H[i]-1, S.query(0, H[i]-1)+A[i])

    print(S.query(0, N))


main()

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, l):
        self.N = 1
        while self.N < len(l):
            self.N *= 2
        self.L = [0 for _ in range(self.N*2-1)]
        for i in range(len(l)):
            self.L[i+self.N-1] = l[i]
        for i in range(self.N-2, -1, -1):
            self.L[i] = max(self.L[i*2+1], self.L[i*2+2])

    def update(self, k, v):
        k += self.N-1
        self.L[k] = v
        while k > 0 and self.L[(k-1)//2] < v:
            k = (k-1)//2
            self.L[k] = v

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

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


dp = [0 for i in range(N)]
S = SegTreeMax(dp)
for i in range(N):
    S.update(H[i]-1, S.query(0, H[i]-1)+A[i])

print(S.query(0, N))

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())

high = list(map(int,input().split()))

beauty = list(map(int,input().split()))

dp = [0]*n

dpcost = copy.copy(beauty)

for i in range(n):
    dp[i] = 1
    for j in range(i):
        #print(i, j)
        if high[j] < high[i]:
            dpcost[i] = max(dpcost[j] + beauty[i], dpcost[i])
            if dp[i] < dp[j]+1:
              dp[i] = dp[j]+1

#print(dp)
print(max(dpcost))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTreeMax:
    def __init__(self, a):
        self.padding =  -float('inf')
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = max(self.data[i], self.data[i-1])
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def search(self, i, j):
        # [i, j)の区間の最小値を求める
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: # idx1が偶数
                result = max(result, self.data[idx1])
            if idx2&1 == 1: # idx2が奇数
                result = max(result, self.data[idx2])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = max(result, self.data[idx1])
        else: # idx1 + 1 == idx2
            result = max(result, self.data[idx1], self.data[idx2])
        
        return result


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

dp = [0] * (N+1)
st = SegmentTreeMax(dp)

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a, mode='min'):
        if mode == 'min':
            self.padding = float('inf')
            self.func = min
        elif mode == 'max':
            self.padding = -float('inf')
            self.func = max
        elif mode == 'sum':
            self.padding = 0
            self.func = sum
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.func([self.data[i], self.data[i-1]])
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.func([self.data[2*idx+1], self.data[2*idx+2]])
    
    def search(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = self.func([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = self.func([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = self.func([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = self.func([result, self.data[idx1], self.data[idx2]])
            
            return result


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

dp = [0] * (N+1)
st = SegmentTree(dp, 'max')

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Submission status: Time Limit Exceeded

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


def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])

def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = 0

#num_max:n以上の最小の2のべき乗
# num_max =2**(n-1).bit_length()
num_max = 2**(len(str(bin(n-1))) -2)
seg_max=[ide_ele_max]*2*num_max

for i in range(n):
    h_i = h[i]
    update_max( h_i-1, query_max(0,h_i) + a[i] )

print(query_max(0,n))

Submission status: Time Limit Exceeded

Solution code:
# Max演算に絞ったsegment treeでもpython3だとTLE？

class SegmentTreeMax:
    def __init__(self, a):
        self.padding =  -float('inf')
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = max(self.data[i], self.data[i-1])
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def search(self, i, j):
        # [i, j)の区間の最小値を求める
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: # idx1が偶数
                result = max(result, self.data[idx1])
            if idx2&1 == 1: # idx2が奇数
                result = max(result, self.data[idx2])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = max(result, self.data[idx1])
        else: # idx1 + 1 == idx2
            result = max(result, self.data[idx1], self.data[idx2])
        
        return result


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

dp = [0] * (N+1)
st = SegmentTreeMax(dp)

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a, mode='min'):
        self.mode = mode
        if self.mode == 'min':
            self.padding = float('inf')
        elif mode == 'max':
            self.padding = -float('inf')
        elif mode == 'sum':
            self.padding = 0
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self._segfunc(*[self.data[i], self.data[i-1]])
    
    def _segfunc(self, *v_list):
        if self.mode == 'min':
            return min(v_list)
        elif self.mode == 'max':
            return max(v_list)
        elif self.mode == 'sum':
            return sum(v_list)
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self._segfunc(
                *[self.data[2*idx+1], self.data[2*idx+2]]
            )
    
    def search(self, i, j):
        # [i, j)の区間の最小値を求める
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: # idx1が偶数
                result = self._segfunc(*[result, self.data[idx1]])
            if idx2&1 == 1: # idx2が奇数
                result = self._segfunc(*[result, self.data[idx2]])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = self._segfunc(result, self.data[idx1])
        else: # idx1 + 1 == idx2
            result = self._segfunc(*[result, self.data[idx1], self.data[idx2]])
        
        return result


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

dp = [0] * (N+1)
st = SegmentTree(dp, mode='max')

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(N+1, dtype=int)

ans = 0
for h, a in zip(H, A):
  dp[h] = np.max(dp[:h]) + a
  ans = max(ans, dp[h])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    sys.setrecursionlimit(100000000)
    N = int(raw_input())
    # N, K = 5000, 100
    HEIGHTS = list(map(int, raw_input().split()))
    BEAUTIES = list(map(int, raw_input().split()))

    max_beauties_cache = {}

    def get_max_remaning_beauties(i, last_height):
        if i >= N:
            return 0

        if (i, last_height) in max_beauties_cache:
            return max_beauties_cache[i, last_height]

        remove_sum = get_max_remaning_beauties(i+1, last_height)
        leftout_sum = 0
        if last_height <= HEIGHTS[i]:
            leftout_sum = get_max_remaning_beauties(i + 1, HEIGHTS[i]) + BEAUTIES[i]

        ans = max(remove_sum, leftout_sum)
        max_beauties_cache[i, last_height] = ans

        return ans


    print get_max_remaning_beauties(0, 0)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

N = int(raw_input())
# N, K = 5000, 100
HEIGHTS = list(map(int, raw_input().split()))
BEAUTIES = list(map(int, raw_input().split()))

max_beauties_cache = {}

def get_max_remaning_beauties(i, last_height):
    if i >= N:
        return 0

    if (i, last_height) in max_beauties_cache:
        return max_beauties_cache[i, last_height]

    remove_sum = get_max_remaning_beauties(i+1, last_height)
    leftout_sum = 0
    if last_height <= HEIGHTS[i]:
        leftout_sum = get_max_remaning_beauties(i + 1, HEIGHTS[i]) + BEAUTIES[i]

    ans = max(remove_sum, leftout_sum)
    max_beauties_cache[i, last_height] = ans

    return ans


print get_max_remaning_beauties(0, 0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        # 単位元
        self.idelem = 0
        # 比較関数
        self.func = max

        self.N0 = 2**(math.ceil(math.log2(N)))
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def solve(N: int, h: "List[int]", a: "List[int]"):

    seg = SegmentTree(N+1)

    for i in range(N):
        temp = a[i] + seg.query(0, h[i])
        seg.update(h[i], temp)
    print(seg.query(0, N+1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, h, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=max):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * (2 * self.n)

        for i in range(self.n):
            self.tree[i+self.n] = seq[i]

        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree([0] * (n+1), op=max)

    for pos, b in zip(heights, beauty):
        best = dp.query(0, pos)
        dp.modify(pos, best + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * (2 * n)
        self.n = n

    def modify(self, pos, val):
        tree = self.tree
        pos += self.n
        tree[pos] = val
        while pos > 1:
            tree[pos//2] = max(tree[pos], tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = max(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = max(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree(n+1)
    for h, b in zip(heights, beauty):
        _max = dp.query(0, h)
        dp.modify(h, _max + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]

dp = list(beauty)

for i in range(n):
    max_beauty = beauty[i]
    for j in range(i):
        if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
            max_beauty = beauty[i] + dp[j]

    dp[i] = max_beauty

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def makeTree(x,y):
    if y>x:
        T[(x,(x+y)//2)]=0
        makeTree(x,(x+y)//2)
        T[((x+y)//2+1,y)]=0
        makeTree((x+y)//2+1,y)
def rmq(r,l,x,y):
    if l<x or r>y:
        return 0
    if r<=x and y<=l:
        return T[(x,y)]
    return max(rmq(r,l,x,(x+y)//2),rmq(r,l,(x+y)//2+1,y))
def udTree(i):
    T[(i,i)] = dp[i]
    x = i
    y = i
    d = 1
    while d<2**n:
        if x%(2*d)==0:
            T[(x,x+2*d-1)] = max(T[(x,x+2*d-1)],T[(x,y)])
            y = x+2*d-1
        else:
            T[(y-2*d+1,y)] = max(T[(y-2*d+1,y)],T[(x,y)])
            x = y-2*d+1
        d = y-x+1
N = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))
Ho = [(i,H[i]) for i in range(N)]
Ho = sorted(Ho,key=lambda x:x[1])
dp = [0 for i in range(N)]
n = math.ceil(math.log2(N))
T = {}
T[(0,2**n-1)] = 0
makeTree(0,2**n-1)
for i in range(N):
    ind = Ho[i][0]
    if ind==0:
        dp[ind] = A[ind]
        udTree(ind)
    else:
        dp[ind] = rmq(0,ind-1,0,2**n-1)+A[ind]
        udTree(ind)
print(T[(0,2**n-1)])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N = int(input())
    h = tuple(map(int, input().split()))
    d = {}
    for i, v in enumerate(h):
        d[v] = i
    a = tuple(map(int, input().split()))
    la = [0] * N
    la[0] = a[0]
    lh = [h[0]]
    for i in range(1, N):
        insert_index = bisect.bisect_left(lh, h[i])
        if insert_index == 0:
            la[i] = a[i]
        else:
            la[i] = max(la[d[lh[j]]] for j in range(insert_index)) + a[i]
        lh.insert(insert_index, h[i])
    return max(la)
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = [0] * H[0] + [A[0]] * (N - H[0] + 1)
    for a, h in zip(A[1:], H[1:]):
        t = dp[h] = dp[h] + a
        for j in range(h + 1, N + 1):
            if dp[j] < t:
                dp[j] = t

    return max(dp)


print(main())