yukicoder No.679 不思議マーケット

No.679 不思議マーケット - yukicoder

n-m個の必ず買わせることができる商品を先に買わせ, 条件を満たしているものから貪欲に買わせることで最大値を得ることができます. 条件を満たしている商品は, 買う順番が少し後になっても条件を満たしたままであることがポイントです. 計算量はO(max(r_i)N^2)になりました.
解説をみるとグラフの強連結成分が〜とか書いてあってそのへんがわかるともっと速いコードが書けるっぽいです.

#278108 No.679 不思議マーケット - yukicoder