[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; }
ディスカッション
コメント一覧
まだ、コメントがありません