# ABC017 C - ハイスコア

# 概要

NN個の遺跡とMM種類の宝石がある.
遺跡iiを探索すると, [lil_i, rir_i]の種類の宝石を11つずつ入手し, スコアsis_iを獲得する.
しかし, 全種類の宝石を入手すると, 獲得したスコアは00になる.
このとき, 獲得できるスコアの最大値を求めよ.

# 解法

方針としては, 全体から必要のない部分を減じるという流れになる.
これは, いもす法で解ける.
まず, 全ての遺跡のスコア等を全て設定する.
次に, いもすテーブルをシミュレーションして求める.
最後に, そのテーブルの最小値を求めて, 全体から減じれば良い.

# 提出

ABC017-C

以上.
お疲れ様でした.

セグ木でも解けるらしい.

Last Updated: 2019-3-14 02:04:59