ねこ鍋。良問だという話を聞いたので考えてみたらごり押し解を思いついたので実装した。 (cuteのmax)-(cuteのmin)で二分探索することを考える。そうすると、O(N)個の区間でナップサックをして、取れる重さの値をオスメスともに列挙できればよいことがわかる…

本番で解けなかった問題。区間DP。解説だと「区間を木にできるかだと4乗になって、区間を森にできるかどうかを考えると3乗に落ちる」と言われていましたが、「区間を木にできるかどうか」だけで3乗にできます。まず、DP[区間][一番最後の子x]: 区間の左端を…