DP Q

Given two sequences of numbers, the problem of choosing the one that maximizes the sum of the given scores in the other sequence among all the subsequences that would be a monotonically increasing sequence of one of the sequences.

As for the small sample problem, this will solve it.

If this max part is naively O(N), the whole thing would be N^2, which is 10^10, so it won't make it.

So use an algorithm that can compute max in log N

code:python

def solve(N, HS, VS):

for i in range(N):

return max(values)

Fennic tree

code:python

def solve(N, HS, VS):

def bit_put(pos, val):

assert pos > 0

x = pos

while x <= N:

x += x & -x # (x & -x) = rightmost 1 = block width

def bit_max(pos):

assert pos > 0

ret = 0

x = pos

while x > 0:

x -= x & -x

return ret

for i in range(N):

m = bit_max(h)

return bit_max(N)

---