みかん [CODE FESTIVAL 2018 qual A B]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_b

前提知識

• imos法（無くても全然解ける）

考察過程

1. なるべくB房みかんを使ったほうが良い
2. A房みかんを使わなくてはいけないのは、M個の区間での話
3. 1つ以上の区間で覆われている部分はA房で、ほかはB房で最適解行けそう

解法

https://beta.atcoder.jp/contests/code-festival-2018-quala/submissions/3242960

「imos[i] := i番目のみかんが何個の区間で覆われているか」を作るために、imos法を用いよう。
imos[i]を0～N-1まで見ていって、1つでも覆われていれば+A, どこにも覆われていないなら+Bする。
これで答え。

int N, M, A, B;
int imos[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> A >> B;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--;
        imos[a]++;
        imos[b]--;
    }
    rep(i, 1, N) imos[i] += imos[i - 1];
 
    int ans = 0;
    rep(i, 0, N) {
        if (imos[i]) ans += A;
        else ans += B;
    }
    cout << ans << endl;
}