問題概要
長さ 
の数列 
が与えられる. この中から総和が等しい区間を複数選ぶとき, 最大でいくつ選べるか？(構築せよ. ) ただし区間同士が重なってはならないものとする.
問題へのリンク
制約
解説
数列の長さが短いので, 区間の数が比較的少なく, 区間和としてとりうる値を全列挙することができます. ただし, これらすべての値についてどう選ぶかを実装しようとすると 
や 
程度になってしまいうまくいきません.
そこで, std::map の key を区間和, value をその区間和をもつ区間 
の vector として持ってみましょう. すると, 区間和を決めうったとき, 複数の区間からなる集合から重ならないようにたくさん選びましょうという問題になり, これは区間スケジューリング問題そのものです.
またこのように実装すると, ある区間についてたかだか 
回しか見ることがないので, 全体としては 回しか見ません. ということで, ソートの分を含めて 
で問題を解くことができました.
実装
Submission #146489204 - Codeforces
