EDPC Q - Flowers

考え方

左から順に、その花を最後に残す場合の最大値を求めていけばよい。
その値は、自分より前にある自分より低い花の中での最大値+自分の価値とすればよい。
$O(N^2)$ でよいのであれば、これで簡単。

あとは高速化だが、最大値を取得できるsegment木を用いるのが有効。
花 $1$ 本を処理するごとに、最後の花の高さが $i$ である場合の情報を位置 $i$ に入れてやる。
すると、「高さが自身未満の中で最大値」を $O(\log N)$ で取得できる。
これで全体計算量は $O(N\log N)$ となる。

最後の答えは、任意の花を最後に残した場合の最大値であり、つまりsegment木の全体処理した値である。

入力例1での動作

入力を受け取り、高さを 0-indexed に直す。

n: 4
h: {2, 0, 3, 1}
a: {10, 20, 30, 40}

seg[x] を、高さ x の花を最後に残す場合の最大価値とする。

最初は全て $0$ である。

seg: {0, 0, 0, 0}

$1$ 本目の花は、高さ 2、価値 10 である。
高さ 2 より低い花で終わる最大価値は $0$ なので、seg[2] を $10$ にする。

seg: {0, 0, 10, 0}

$2$ 本目の花は、高さ 0、価値 20 である。
高さ 0 より低い花はないので、seg[0] を $20$ にする。

seg: {20, 0, 10, 0}

$3$ 本目の花は、高さ 3、価値 30 である。
高さ 3 より低い花で終わる最大価値は $20$ なので、seg[3] を $50$ にする。

seg: {20, 0, 10, 50}

$4$ 本目の花は、高さ 1、価値 40 である。
高さ 1 より低い花で終わる最大価値は $20$ なので、seg[1] を $60$ にする。

seg: {20, 60, 10, 50}

全体の最大値 $60$ が答えである。

注意点

答えは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。