C

愚直に解くと、すべての開始点から条件内に収まる限り部分文字列をインクリメントしていく方法（[tex:N²]）で解けそう。

開始点をインクリメントする際に、部分列の積をまた始めから計算しなおすのではなく、一つ前の値で割ることで、無駄な計算を省くことができる。（O(N)）

D

蟻本でやったことがあったので簡単に解けるかなと思ったが、3つのパターンそれぞれ解法を考える必要があるということで、本の内容より複雑で苦戦した。

なので、DPを解く際に気をつけることを整理。

Nが小さく、W, V が大きい場合に上記のDPは使えない。

N <= 30 なので、2³⁰ だと大きすぎるので、荷物を半分に分割し、前半後半部分の組み合わせを工夫することで、計算量を抑える。

まず前半部分荷物の全組み合わせを集計し、後半部分で、残りの重さでの二分探索ができるように整理する。

（重さでソートした後に、より低い重量で、高い価値があるような組み合わせは排除する。vectorの2分探索は lower_bound で求めることが可能）

後半部分の組み合わせ集計後に、残り重量でのベストな前半部分の価値を二分探索で求め、足し合わせたものの中から MAX を求める。