A
dfsっぽくやって途中でexitすれば速いです。
B
InteractiveっぽかったのでSkip
C
なんでこれ解けないのかなぁ…。
dp[at][count]:=atまで見た時count個stackしたとする。その時の重さの最小値でO(N^2)で、実はcount<=200と言えるので間に合うという、定番中の定番だったけど全然見えなかったです。
まず謎貪欲を考えてしまったのが原因。最初に一番条件が厳しそうなやつを固定して…という方針をとりました。これで不等式をごちゃごちゃしていたんですが、O(N^3)から改善できませんでした。
出てきた不等式が固定したものに依存する形だったのでO(N^2)かかるはずだと冷静に考えればわかるんですが、本番はそこから抜け出せなかったですね。
終了1時間前にめでたくdp思いついたんですが、そこからO(N^2)を改善できなかったのもだめでした。
O(N^2)のdpの改善は累積和or segtree or 状態削減ってわかっているんですが実践できませんでしたね。
こういう泥沼から逃れるための方法がほしいなぁ。
今回の経験で学んだことは「不等式は単調性が成り立つ時のみしかほとんど有用ではない」ってことですね。
