ukuku09コンテスト 001-photography
区間と言われたので累積和を取りたくなる。累積和をSで書くことにするとl番目の要素を区間の左端とするとき P+S[l-1] 以上のもっとも右にある要素の位置が分かればl番目が区間の左端のときの最適な区間が求まる。右端がO(1)かO(logn)くらいで求められればできそう。累積和がN以上のもっとも右にある要素の位置を持っておけばよさそう。累積和の値は大きすぎて配列でもつのは不可能なのでmapでもつ。
累積和を取ったあと後ろから見ていって、今まで見た中で一番大きい値であれば更新してmapに値を設定する。mapを使えば区間の左端を指定した時に二分探索すれば右端がO(logn)でわかるのでO(nlogn)でできる。
（嘘解法じゃないかちょっとこわい）
