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

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

    # INT_MIN = -10 ** 18
    MAX_N = 2 * 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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def main():
    input()
    H=map(int,input().split())
    A=map(int,input().split())
    n=10**5+1

    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 =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    for h,a in zip(H,A):
        update_max(h,query_max(0,h)+a)
    
    print(query_max(0,n))
main()

Submission status: Runtime Error

Solution code:
def main():
    input()
    H=map(int,input().split())
    A=map(int,input().split())
    n=10*5+1

    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 =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    for h,a in zip(H,A):
        update_max(h,query_max(0,h)+a)
    
    print(query_max(0,n))
main()

Submission status: Runtime Error

Solution code:
INF = 10**9

class RMQ:
    def __init__(self, n):
        self.n = n 
        self.size = 2**(self.n - 1).bit_length()
        self.data = [INF] * (2*self.size-1)

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n = int(input())
h_s = [int(item) for item in input().split()]
a_s = [int(item) for item in input().split()]

rmq = RMQ(10**5 + 10)
for i, (h, a) in enumerate(zip(h_s, a_s)):
    beaut = rmq.query(0, h)
    if beaut == INF:
        rmq.update(h-1, -a)
    else:
        rmq.update(h-1, beaut - a)

print(-rmq.data[0])

Submission status: Runtime Error

Solution code:
n=int(input())

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

dp=[-1]*n

def f(x):
	if dp[x] == -1:
		maxi = 0
		for i in range(x+1, n):
			if h[i] < h[x]:
				continue
			else:
				maxi = max(maxi, f(i) + a[x])
		maxi = max(maxi, a[x])
		dp[x] = maxi
	return dp[x]
	


print(max([f(i) for i in range(n)]))
#print(dp)

Submission status: Runtime Error

Solution code:
def get(i):
    mx = 0
    while i > 0:
        if bit[i] > mx:
            mx = bit[i]
        i -= i & -i
    return mx


def update(i, x):
    while i < n + 1:
        if x > bit[i]:
            bit[i] = x
        i += i & -i


def f(hs, a_s):
    for h, a in zip(hs, a_s):
        update(h, get(h - 1) + a)
    print(max(bit))


n = int(input())
hs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
bit = [0] * (n + 1)
f(n, hs, a_s)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [set() for _ in range(N)]
    for i in range(M):
        x, y = map(int, input().split())
        adj[x-1].add(y-1)
        adj[y-1].add(x-1)
    path = [-1] * N
    q = [(-(S-1), S-1)]
    while len(q):
        minimum, cur = heappop(q)
        minimum = -minimum
        if minimum <= path[cur]:
            continue
        path[cur] = minimum
        for a in adj[cur]:
            heappush(q, (-min(minimum, a), a))
    for i in range(N):
        if path[i] == i:
            print(i+1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:


tests = int(input())

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

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

    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

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

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

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

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

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

    return(getmax(0, n))

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

Submission status: Runtime Error

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

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -float("inf")
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))

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

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

print(max(dp))