解法
文字目を
"1"にした場合に、で得られる得点の最大値
を考えます。
すると、
が間に含まれているものを除いた区間達について計算した場合の、
で得られる得点の最大値に、
が間に含まれている区間の得点の総和が、
の値になります。
これを上手く計算するには、
を計算する
を満たす全ての
について、
に
を加算する
という操作を、が小さい方から順番に繰り返していけば良いです。
このようにすることで、それぞれの区間が重複して加算されるのを防ぐことができます。
答えは、の中で最大のものを計算すればよいです。
感想
区間の重複加算を防ぐ方法を思いつくのに時間がかかりました…セグ木は便利ですね！
