Q - Flowers

  • 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 - Fennic tree python
def solve(N, HS, VS):
    values = [0] * (N + 1)
    for i in range(N):
        h = HS[i]
        values[h] = max(values[:h]) + VS[i]

    return max(values)

Fennic tree python

def solve(N, HS, VS):
    bit = [0] * (N + 1)  # 1-origin

    def bit_put(pos, val):
        assert pos > 0
        x = pos
        while x <= N:
            bit[x] = max(bit[x], val)
            x += x & -x  # (x & -x) = rightmost 1 = block width

    def bit_max(pos):
        assert pos > 0
        ret = 0
        x = pos
        while x > 0:
            ret = max(ret, bit[x])
            x -= x & -x
        return ret

    for i in range(N):
        h = HS[i]
        m = bit_max(h)
        bit_put(h, m + VS[i])

    return bit_max(N)

AC https://atcoder.jp/contests/dp/submissions/15080447


This page is auto-translated from [/nishio/DP Q](https://scrapbox.io/nishio/DP Q) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.