Educational DP Contest Q - Flowers
各点でその点を最後に使った場合の美しさの和を求める
ある点で上の美しさを求めるには、自信より左にあって高さが自分未満の中で一番総和の高いものに自身の美しさを加える
最後に全部の点の中で一番総和の高いものが答えになる
愚直にやると$ O(N^2)で$ 4\times 10^{10}ほどになって間に合わない
セグ木を使うと$ O(N\log N)で間に合う
問題: https://atcoder.jp/contests/dp/tasks/dp_q
提出: https://atcoder.jp/contests/dp/submissions/6916875
#EDPC #AtCoder