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 main():
    n = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x >= y:
            return x
        else:
            return y

    def init(init_val):
        # set_val
        for i in range(n+1):
            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[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while p < q:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 0

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

    X = [0]*(n+1)
    for i in range(n):
        update(H[i], query(0, H[i]+1)+A[i])
    print(query(0, n+2))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    import sys

    def input(): return sys.stdin.readline().strip()
    def list2d(a, b, c): return [[c] * b for i in range(a)]
    def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
    def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
    def ceil(x, y=1): return int(-(-x // y))
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
    def Yes(): print('Yes')
    def No(): print('No')
    def YES(): print('YES')
    def NO(): print('NO')
    sys.setrecursionlimit(10 ** 9)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7

    class BIT:
        """ BIT汎用版 """

        def __init__(self, n, func, init):
            # 0-indexed
            n += 1
            nv = 1
            while nv < n:
                nv *= 2
            self.size = nv
            self.func = func
            self.init = init
            self.tree = [init] * nv

        def query(self, i):
            """ [0, i]の値を取得 """
            s = self.init
            i += 1
            while i > 0:
                s = self.func(s, self.tree[i-1])
                i -= i & -i
            return s

        def update(self, i, x):
            """ 値の更新：添字i, 値x """
            i += 1
            while i <= self.size:
                self.tree[i-1] = self.func(self.tree[i-1], x)
                i += i & -i

    N = INT()
    H = LIST()
    A = LIST()

    bit = BIT(N+1, max, 0)
    for h, a in zip(H, A):
        # ここより手前で出現した自分より低い花から、一番いいところを取る
        mx = bit.query(h)
        # 自身の最善の値を更新
        bit.update(h, mx + a)
    ans = bit.query(N)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

n=int(input())
h=list(map(int,input().split()))
b=list(map(int,input().split()))
new_arr=[]
for i in range(n):
    new_arr.append([h[i],b[i],i])
new_arr.sort(key=lambda x: x[0])
new_arr=new_arr[::-1]

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


for seq in new_arr:
    idx=seq[2]
    ans[idx]=max(ans[idx::])+seq[1]
print(max(ans))

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i

N = INT()
H = LIST()
A = LIST()

bit = BIT(N+1, max, 0)
for h, a in zip(H, A):
    # ここより手前で出現した自分より低い花から、一番いいところを取る
    mx = bit.query(h)
    # 自身の最善の値を更新
    bit.update(h, mx + a)
ans = bit.query(N)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
d=[0]*-~n
for h,a in zip(a,a[n:]):
 i,s=h,0
 while i:s=max(s,d[i]);i-=i&-i
 while h<=n:d[h]=max(d[h],s+a);h+=h&-h
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())+1
    dp=[0]*n*2
    for h,a in zip(map(int,input().split()),map(int,input().split())):
        l,r,s=n,h+n,0
        while l<r:
            if l&1:
                t=dp[l]
                if t>s:s=t
                l+=1
            if r&1:
                r-=1
                t=dp[r]
                if t>s:s=t
            l>>=1
            r>>=1
        s+=a
        i=h+n
        if s>dp[i]:
            dp[i]=s
            i>>=1
            while i:
                s,t=dp[i+i],dp[i-~i]
                if t>s:s=t
                if s>dp[i]:dp[i]=s
                else:break
                i>>=1
    print(dp[1])
main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    n,*a=map(int,open(0).read().split())
    dp=SegTree(n+1,0,lambda a,b:a if a>b else b)
    for h,a in zip(a,a[n:]):dp.update(h,dp.query(0,h)+a)
    print(dp.data[1])
main()

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

st = SegmentTree([0]*2*(10**5), max, 0)

for _, a, i in sorted(zip(H, A, range(N))):
    st.update(i, st.query(0, i) + a)

print(st.query(0, N))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
h = np.array(list(map(int, input().split())), dtype='int64')
a = np.array(list(map(int, input().split())), dtype='int64')

dp = np.zeros((n, 2), dtype='int64')
dp[0][0] = a[0]
dp[0][1] = a[0]

for i in range(1, n):
    h_ = h[:i]
    js = np.where(h_ < h[i])[0]
    if len(js) == 0:
        dp[i][1] = a[i]
    else:
        dp[i][1] = np.max(np.array(dp[js, 1])) + a[i]
    dp[i][0] = max(dp[i][1], dp[i-1][0])

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
h = np.array(list(map(int, input().split())), dtype='int64')
a = np.array(list(map(int, input().split())), dtype='int64')

dp = np.zeros((n, 2), dtype='int64')
dp[0][0] = a[0]
dp[0][1] = a[0]

for i in range(1, n):
    h_ = h[:i]
    js = np.where(h_ < h[i])[0]
    if len(js) == 0:
        dp[i][1] = a[i]
    else:
        dp[i][1] = max(dp[js, 1]) + a[i]
    dp[i][0] = max(dp[i][1], dp[i-1][0])

print(dp[-1][0])

Submission status: Time Limit Exceeded

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

t = 1
while t <= n:
    t *= 2
dp = [float('-inf')] * (2 * t - 1)

up = lambda node: (node - 1) // 2
down = lambda node: (node * 2 + 1, node * 2 + 2)

def update(i, x):
    i += t - 1
    dp[i] = x
    while i != 0:
        i = up(i)
        c = down(i)
        dp[i] = max(dp[c[0]], dp[c[1]])

def find(l, r, node=0, sl=0, sr=t):
    if sr <= l or r <= sl:
        return float('-inf')
    if l <= sl and sr <= r:
        return dp[node]
    sc = (sl + sr) // 2
    c = down(node)
    return max(
        find(l, r, c[0], sl, sc),
        find(l, r, c[1], sc, sr),
    )

# dp = []
# for i in reversed(range(n)):
#     maxv = 0
#     for height, value in dp:
#         if h[i] < height:
#             maxv = max(maxv, value)
#     dp += [[h[i], maxv + a[i]]]
# print(dp)

for i in reversed(range(n)):
    maxv = max(find(h[i], t), 0) + a[i]
    update(h[i], maxv)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst)
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N - 1 elements
        tree = [self.e] * (self.N - 1) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 2, -1, -1):
            tree[i] = self.op(tree[2*i + 1], tree[2*i + 2])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N - 1]
    
    # update a_i to be x 
    def update(self, i, x):
        i += self.N - 1
        self.v[i] = x
        while i > 0:
            i -= 1; i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
    
    # returns answer for the query interval [l, r)
    def query(self, l, r):
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e; R = self.e
        while left < right:
            if left & 1 == 0: # self.v[left] is the right child
                L = self.op(L, self.v[left])
                left += 1
            if right & 1 == 0: # self.v[right-1] is the left child
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1; left >>= 1
            right >>= 1
        return self.op(L, R)

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

H = coord_compress(H)
dp = SegmentTree([0] * len(H), max, 0)
for h, a in zip(H, A):
    dp.update(h, max(dp[h], dp.query(0, h) + a))
print(max(dp))

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 = 1
# while n <= N:
#     n *= 2

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

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

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

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

# ans = 0

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

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

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 = 1
# while n <= N:
#     n *= 2

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

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

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

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

# ans = 0

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

print (max(dp))

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 = 1
# while n <= N:
#     n *= 2

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

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

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

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

# ans = 0

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

print (max(dp))

Submission status: 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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0

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

print (max(dp))

Submission status: 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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0

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

print (max(dp))

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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0

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

print (max(dp))

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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0

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

print (query(1, N + 1))

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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0
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, query(1, h + 1) + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

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 = 1
while n <= N:
    n *= 2

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

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

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

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

# ans = 0
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 (query(1, N + 1))

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 = 1
while n <= N:
    n *= 2

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

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

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        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 (query(1, N + 1))

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 * n - 1)

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

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        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 (query(1, N + 1))

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 * 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
    elif 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 (query(1, N + 1))

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

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)