<a href="https://atcoder.jp/contests/kupc2017/tasks/kupc2017_h">H - Make a Potion</a>
<img src="https://gyazo.com/f2dc4a6aa7acee93e06792643d101b59/thumb/1000" alt="image">
<ul>
<li>考えたこと<ul>
<li>最小カットに帰着できることは既知</li>
<li>選択肢が二択ではないが、<a href="/ja/%E6%9C%80%E5%B0%8F%E3%82%AB%E3%83%83%E3%83%88%E3%81%A73%E4%BB%A5%E4%B8%8A%E3%81%AE%E9%81%B8%E6%8A%9E%E8%82%A2">最小カットで3以上の選択肢</a>でよい</li>
<li>しかしvの範囲が10^6まであるので全部頂点にすると辛い</li>
<li>制約に関係する頂点だけを選ぶ<a href="/ja/%E5%BA%A7%E6%A8%99%E5%9C%A7%E7%B8%AE">座標圧縮</a>が必要か<ul>
<li>効力がプラスなら、制約ギリギリa-1まで入れた方が得</li>
<li>効力がマイナスなら制約ギリギリbで止めるのが得</li>
</ul>
</li>
</ul>
</li>
<li>実装<ul>
<li><img src="https://gyazo.com/9691ec6d4f71c67caf7c82d036afbba4/thumb/1000" alt="image">
</li>
<li><img src="https://gyazo.com/8ca69974b4a52090025c6d4f0c93111b/thumb/1000" alt="image">
</li>
<li>頂点数が不規則なのが実装めんどくさい…
</li>
</ul>
</li>
</ul>

💻KUPC2017H