AtCoder Beginner Contest 17 C - ハイスコア

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の5日目のエントリです．

CODE THANKS FESTIVALに向かう新幹線の中から．

問題要約

N個の宝石とM種類の宝石がある
i番目の遺跡に訪れるとli番目からri番目の宝石が全て手に入りsi点もらえる
全ての宝石を手に入れないように点数を最大化する

解法

まず，全ての遺跡に訪れた場合を考える．次に，i番目の宝石を手に入れない場合点数はどうなるかを考える．例えば以下の入力では，

[code lang=text] 2 3 1 2 10 2 3 20 [/code]

全ての遺跡に訪れた場合，点数は30点だが全ての宝石を手に入れてしまう．
1を手に入れない場合は遺跡1に訪れないことになるため，失う点数は10点．
2を手に入れない場合は遺跡1, 2の両方に訪れないことになるため失う点数は30点．
3を手に入れない場合は遺跡2を訪れないことになるため，失う点数は20点である．
つまり，宝石iが何点に影響しているかを考え，最も小さい宝石を手に入れなければよい．
そのような処理はいもす法で実現できる (セグメントツリーでも可能だけど101点は取れないかもしれない)．