ABC 401-500/ABC439E - Kite - 競技プログラミング用 知識集積所

---

問題

ABC439E

必要知識

B以下レベルの内容は省略

• 最長増加部分列

考え方

何人かを選んで、AもBも増加列になるように選べばよい。
これは、あらかじめAが小さい順に並べ替え、その中でBの最長増加部分列を探せばよい。
問題はAに重複がある場合のタイブレークだが、これはBが大きい方が前になるようにすることで、Aの値がダブっている人を2人選んでしまうことを防げる。

よって、(A,-B)のpair型※をソートし、そこからBの値だけ取り出したvectorを作り、あとは最長増加部分列を求めるだけ。

解答例

解答例

注意点

別解