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

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


sellogn = []
seln = 0
selfunc = max
selone = 0
selb = []


def __init__(a, func=max, one=-10 ** 18):
    global sellogn, seln, selfunc, selone, selb
    sellogn = (len(a) - 1).bit_length()
    seln = 1 << sellogn
    selfunc = func
    selone = one

    selb = [selone] * (2 * seln - 1)
    for i, j in enumerate(a):
        selb[i + seln - 1] = j
    for i in reversed(range(seln - 1)):
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def get_item(i):
    global sellogn, seln, selfunc, selone, selb
    return selb[i + seln - 1]


def update(index, x):
    global sellogn, seln, selfunc, selone, selb
    i = index + seln - 1
    selb[i] = x
    while i != 0:
        i = (i - 1) // 2
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def update_func(index, x):
    global sellogn, seln, selfunc, selone, selb
    i = index + seln - 1
    selb[i] = selfunc(selb[i], x)
    while i != 0:
        i = (i - 1) // 2
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def get_segment(l, r):
    global sellogn, seln, selfunc, selone, selb
    l += seln
    r += seln
    s = selone
    t = selone
    while l < r:
        if l & 1:
            s = selfunc(s, selb[l - 1])
            l += 1
        if r & 1:
            r -= 1
            t = selfunc(selb[r - 1], t)
        l >>= 1
        r >>= 1
    return selfunc(s, t)


__init__([0]*(n+1))

for i in range(n):
    j = get_segment(0, h[i] + 1)
    update_func(h[i], j + a[i])
print(get_segment(0, n+1))

Submission status: Time Limit Exceeded

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

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


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))

Submission status: Time Limit Exceeded

Solution code:

def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


import sys
sys.setrecursionlimit(10**6)
from collections import  defaultdict


n=int(input())
H=list(map(int,input().strip().split(" ")))
B=list(map(int,input().strip().split(" ")))
d=defaultdict(int)
def find(i,h):
    if i<0:
        return 0
    if h==1:
        return 0
    if d[(i,h)]:
        return d[(i,h)]
    if H[i]<h:
        d[(i,h)]=max(find(i-1,h),find(i-1,H[i])+B[i])
    else:
        d[(i,h)]=find(i-1,h)
    return d[(i,h)]
inf=10**6

print(find(n-1,inf))

Submission status: Time Limit Exceeded

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

dp=[0 for _ in range(N+1)]

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

print(max(dp))

Submission status: Time Limit Exceeded

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

# dp[i] = 高さiのときの最大価値
# 順に見ていって、高さH[i]が来た時に、dp[i - 1]の最大値(美しさ)にA[i]を足したものをdp[i]に入れる
# セグメント木

# 求める値によって以下を書き換える
# DEF=結果に影響を与えない初期値(ex.最小値を求める場合INF)
# __choose__():結果の算出ロジック(ex.最小値を求める場合return min(a,b))
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=0
  def __init__(self,arr):
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    return max(a,b)
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=self.n-1
    
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print(self.tree)
    
N = int(readline())
H = list(map(int,readline().split()))
A = list(map(int,readline().split()))

dp = [0] * (N + 1)
ST = SegmentTree(dp)

for i in range(len(H)):
  h = H[i]
  a = A[i]
  # そこまでの最大値を求める
  maxval = ST.get_val(0,h)
  ST.update(h, maxval + a)

print(ST.get_val(0, N + 1))

Submission status: Time Limit Exceeded

Solution code:
def maxSumIS(arr1,arr2, n): 
    max = 0
    msis = [0 for x in range(n)] 
  
    # Initialize msis values 
    # for all indexes 
    for i in range(n): 
        msis[i] = arr2[i] 
  
    # Compute maximum sum  
    # values in bottom up manner 
    for i in range(1, n): 
        for j in range(i): 
            if (arr1[i] > arr1[j] and
                msis[i] < msis[j] + arr2[i]): 
                msis[i] = msis[j] + arr2[i] 
  
    # Pick maximum of 
    # all msis values 
    for i in range(n): 
        if max < msis[i]: 
            max = msis[i] 
  
    return max

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
print(maxSumIS(A,B,N))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
st=SegmentTreeMax(max(h)+1,0)
for i in range(n):
  val=a[i]+st.query(0,h[i]-1)
  st.update(h[i],val)
print(max(st.tree))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = [0] * (N + 1)  # 最大の高さのものがj以下のときの美しさの最大値
    for i in range(N):  # 花のNo.
        h = H[i]  # takasa
        a = A[i]  # beauty
        for j in range(h):
            dp[h] = max(dp[j] + a, dp[h])

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s

def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = SegTree([0] * N, max)

    for h, a in zip(H, A):
        S.update(h - 1, S.query(0, h - 1) + a)
    return S.query(0, N)

print(main())

Submission status: Time Limit Exceeded

Solution code:

import operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def update(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


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

    Flowers = []
    for i in range(N):
        Flowers.append((H[i], (A[i], i)))
    # 高さを昇順にソート
    Flowers.sort()

    seg = SegmentTree(N, fn=max)
    for i in range(N):
        h, (a, idx) = Flowers[i]
        maxV = seg.get(0, idx)
        # l=0, r=0 の時Noneを返す仕様
        if maxV == None:
            maxV = 0
        seg.set(idx, maxV+a)

    ans = seg.get(0, N)
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
class Segtree():  # Segtree

    def segfunc(self, x, y):  # 区間にしたい操作
        return max(x, y)  # ex) max,min,gcd,lcm,sum,product

    def __init__(self, LIST, ide_ele):  # LIST: 配列の初期値, ide_ele: 単位元
        n = len(LIST)
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):  # 配列の値を葉にセット
            self.tree[self.num + i] = LIST[i]
        for i in range(self.num - 1, 0, -1):  # 構築していく
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):  # k番目の値をxに更新
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):  # [l, r)のsegfuncしたものを得る
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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

dp = Segtree([0] * (n + 1), 0)
for ai, hi in zip(a, h):
    dp.update(hi, dp.query(0, hi) + ai)
print(dp.query(0, n + 1))

Submission status: Time Limit Exceeded

Solution code:
class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = -(10 ** 18)  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Max_Bit(N)
for i in range(N):
    dp.update(i+1,A[i])
for i in range(2,N + 1):
    mask = []
    for j in range(1, i):
        if H[i-1] >= H[j-1]:
            mask.append(j)
    if mask:
        dp.update(i, max([dp.tree[k] for k in mask]) + A[i-1])
print(dp.get_max())

Submission status: Time Limit Exceeded

Solution code:
class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = -(10 ** 18)  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Max_Bit(N)
for i in range(N):
    dp.update(i+1,A[i])
for i in range(2,N + 1):
    for j in range(1, i):
        if H[i-1] >= H[j-1]:
            dp.update(i, dp.tree[j] + A[i-1])
print(dp.get_max())

Submission status: Time Limit Exceeded

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal

# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13

# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''


def inp():
    return(int(input()))
def inlt(): 
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def insr2():
    s = input()
    return((s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
############ ---- Input Functions ---- #######End
# #####   

def seg_fun(fun,a,b):
    if fun == "max":
        return max(a,b)
    elif fun == "min":
        return min(a,b)
    elif fun == "sum":
        return a+b
def build_seg_tree(arr,n,fun) : 
    # insert leaf nodes in tree  
    tree = [ 0 for i in range(2*n)]
    for i in range(n) :  
        tree[n + i] = arr[i]  
    # build the tree by calculating parents  
    for i in range(n - 1, 0, -1) :  
        tree[i] = seg_fun(fun,tree[i << 1],tree[i << 1 | 1])
        # tree[i] = tree[i << 1] + tree[i << 1 | 1]
    return tree  
  
# function to update a tree node  
def updateTreeNode(p, value,tree,n,fun) :  
    # set value at position p  
    tree[p + n] = value;  
    p = p + n;  
    # move upward and update parents  
    i = p
    while i > 1 : 
        tree[i >> 1] = seg_fun(fun,tree[i],tree[i ^ 1])
        # tree[i >> 1] = tree[i] + tree[i ^ 1];  
        i >>= 1;  
    return tree
  
# function to get sum on interval [l, r)  
def query(l, r,tree,n,fun) :  
    if fun == "max":
        res = -1*sys.maxsize
    if fun == "min":
        res = sys.maxsize
    if fun == "sum":
        res = 0
    # loop to find the sum in the range  
    l += n; 
    r += n; 
    while l < r : 
        if (l & 1) : 
            # res += tree[l]  
            res = seg_fun(fun,res,tree[l])
            l += 1
      
        if (r & 1) : 
            r -= 1
            # res += tree[r]  
            res = seg_fun(fun,res,tree[r])
              
        l >>= 1
        r >>= 1
      
    return res;  


def pr_list(a):
    print(*a, sep=" ")
def main():
	# tests =  inp()
    tests = 1
    mod = 1000000007
    limit = 10**18
    ans = 0
    for test in range(tests):
        n = inp()
        h = inlt()
        a= inlt()
        dp = [-1*sys.maxsize for i in range(n+1)]
        tree = build_seg_tree(dp,len(dp),"max")
        
        ans = 0
        for i in range(0,n):
            dp[h[i]] = max(0, query(0, h[i],tree,len(dp),"max")) + a[i]
            ans = max(dp[h[i]],ans)
            tree = updateTreeNode(h[i], dp[h[i]],tree,len(dp),"max")
            # print(h[i],tree)

    print(ans)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout 
from bisect import bisect,bisect_left,bisect_right
def gt(): return map(int, stdin.readline().split())
def gi(): return int(stdin.readline())
def gl(): return list(map(int, stdin.readline().split())) 
def gs(): return stdin.readline()
def getmax(BITTree,i): 
    s = 0
    i = i+1
    while i > 0:
        s = max(s,BITTree[i])
        i -= i & (-i) 
    return s 

def updatebit(BITTree , n , i ,v): 
    i += 1
    while i <= n: 
        BITTree[i] = max(v,BITTree[i]) 
        i += i & (-i) 
def construct( n): 
    BITTree = [0]*(n+1) 
    # for i in range(n): 
    #     updatebit(BITTree, n, i, arr[i])
    return BITTree 
n=gi()
h=gl()
a=gl() 
BITTree = construct(max(h)+1)
for i in range(n):
    updatebit(BITTree,max(h)+1,h[i],getmax(BITTree,h[i]-1)+a[i])
ans=0
print(max(BITTree))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h = list(map(int,input().split()))
h1 = [[h[i],i] for i in range(n)]
h1.sort()
a = list(map(int,input().split()))
dp = [0]*n
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    def max(self, i):
        # [0, i) の要素の最大値を返す
        s = 0
        i += 1
        while i>0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] = max(x,self.tree[i])
            i += i & -i
bit = Bit(n+1)

for i in range(n):
    s = h1[i][1]
    x = a[s]+bit.max(s-1)
    dp[s] = x
    bit.add(s,x)
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h = list(map(int,input().split()))
h1 = [[h[i],i] for i in range(n)]
h1.sort()
a = list(map(int,input().split()))
dp = [0]*n
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    def max(self, i):
        # [0, i) の要素の最大値を返す
        s = 0
        i += 1
        while i>0:
            s = max(s,self.tree[i])
            i -= i & -i
        return s
 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] = max(x,self.tree[i])
            i += i & -i
bit = Bit(2*n+1)

for i in range(n):
    s = h1[i][1]
    x = a[s]+bit.max(s-1)
    dp[s] = x
    bit.add(s,x)
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:


class SegmentTree:

    def __init__(self, array, aggregator):
        self.array = array
        self.aggregator = aggregator
        N = 1
        while N < len(array):
            N *= 2
        self.tree = [0]*(2*N-1)
        self.construct_tree(0, len(array)-1, 0)

    def construct_tree(self, low, high, pos):
        if low == high:
            self.tree[pos] = self.array[low]
        else:
            mid = (low+high)//2
            self.construct_tree(low, mid, 2*pos+1)
            self.construct_tree(mid+1, high, 2*pos+2)
            self.tree[pos] = self.aggregator(self.tree[2*pos+1],
                                             self.tree[2*pos+2])

    def query(self, qlow, qhigh):
        return self._query(qlow, qhigh, 0, len(self.array)-1, 0)

    def _query(self, qlow, qhigh, low, high, pos):
        if qlow <= low and high <= qhigh:
            return self.tree[pos]
        if qlow > high or qhigh < low:
            return 0
        mid = (low+high)//2
        return self.aggregator(self._query(qlow, qhigh, low, mid, 2*pos+1),
                               self._query(qlow, qhigh, mid+1, high, 2*pos+2))


    def update(self, index, value):
        self._update(index, value, 0, len(self.array)-1, 0)

    def _update(self, index, value, low, high, pos):
        if index < low or index > high:
            return
        if low == high:
            self.tree[pos] = value
        else:
            mid = (low+high)//2
            self._update(index, value, low, mid, 2*pos+1)
            self._update(index, value, mid+1, high, 2*pos+2)
            self.tree[pos] = self.aggregator(self.tree[2*pos+1], self.tree[2*pos+2])

    def __str__(self):
        start, end = 0, 1
        levels = []
        while end-1 <= len(self.tree):
            levels.append(self.tree[start:end])
            start, end = end, end+(end-start)*2
        return '\n'.join(map(str, levels))


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    h = read_ints()
    a = read_ints()
    segment_tree = SegmentTree([0]*(N+1), max)
    max_beauty = 0
    for i in range(N):
        beauty = segment_tree.query(0, h[i]-1)+a[i]
        segment_tree.update(h[i], beauty)
        max_beauty = max(max_beauty, beauty)
    return max_beauty


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()

ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  c=y+co[i]
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,c)
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(2*2**(n-1).bit_length())
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(ans)