[AtCoder] ABC 188 D – Snuke Prime

問題

方針

プライムの加入が最適である期間は、期間内で利用するサービスの料金が \( C \) 円を超えるときです。なので、プライムに加入するかどうかを決める時点は \( a_i, b_i \) の値だけを考えれば良いです。

\( m_i \) を \( i \) 日目におけるサービスの料金の変化量とします。これはマップを用いて、

\[ \begin{eqnarray}
m(a_i – 1) &\leftarrow& m(a_i – 1) + c_i \\
m(b_i) &\leftarrow& m(b_i) – c_i
\end{eqnarray}\]

と計算することができます。これを用いて、サービスの料金の累積和を計算し、その値が \( C \) より大きければその期間プライムに加入します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> v;
    map<ll, ll> m;
    ll a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        v.push_back(a);
        m[a - 1] += c;
        m[b] -= c;
    }
    ll cost = 0;
    ll total = 0;
    vector<pair<ll, ll>> p;
    for (auto it = m.begin(); it != m.end(); it++) {
        p.push_back(make_pair(it->first, it->second));
    }
    for (int i = 0; i < p.size() - 1; i++) {
        cost += p[i].second;
        if (cost < C) {
            total += cost * (p[i + 1].first - p[i].first);
        } else {
            total += C * (p[i + 1].first - p[i].first);
        }
    }
    cout << total << "\n";
    return 0;
}