peroon https://blog.hatena.ne.jp/peroon/ perogram https://perogram.hateblo.jp/ if(sw <= W){ ll tv = (lower_bound(ps,ps+m,pll(W-sw,INF))-1)->second; res = max(res,sv+tv); } 後半、こういう箇所がありますよね -1を引くとどうなるか。イテレータの1つ手前を指す 「W-swピッタリの重さがあったら、-1しちゃダメなのでは？」と疑問を持つ それは勘違いで、INFがポイント 重さピッタリのものがlower_boundの範囲内で見つかったとしても、第二引数(pair.second)がINFなので、その値は絶対に見つからない 例：重さ120を探した時、pair(120, INF)でlower_… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fperogram.hateblo.jp%2Fentry%2F2019%2F05%2F18%2F091641" title="蟻本 巨大ナップサック p149 lower_bound - perogram" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-05-18 09:16:41 rich https://perogram.hateblo.jp/entry/2019/05/18/091641 1.0 100%