abc017_3

考えたこと

スコアを最大化したいが、区間にフラグが立って、すべてのフラグが立つとNG

Nが8で部分点。この場合2^8通りを探索することができる

N,Mが5000で別の部分点、10万で満点

もしも区間がカバーしない点があれば自明に「全部選択する」が最良

区間がすべてをカバーするケースを考えると、どこか1箇所カバーされない点ができるように穴を開ければ良い

穴を1箇所選べば、それに重なってる区間はすべて外すことが必要だし、それで十分、この時スコアは全部選択した時と比べて「重なってる区間」のスコアの和だけ減る

よってスコアを区間に足し合わせて、最小値を見つける問題

カバーしてない点がある場合は最小値が0になるので場合分けは必要ない

公式解説OK