Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //https://atcoder.jp/contests/abc188/tasks/abc188_d
- #include <bits/stdc++.h>
- #include <time.h>
- using namespace std;
- #define int long long
- /*
- #define inp_file
- #define op_file
- */
- int _solve()
- {
- /*
- #ifndef ONLINE_JUDGE
- freopen(inp_file, "r", stdin);
- freopen(op_file, "w", stdout);
- #endif
- */
- int N, C;
- cin >> N >> C;
- vector<pair<int, pair<int, int> > > vi;
- for (int i = 0;i < N; i++) {
- int st, en, c;
- cin >> st >> en >> c;
- vi.push_back({st, {0, c}});
- vi.push_back({en, {1, c}});
- }
- sort(vi.begin(), vi.end());
- pair<int, pair<int, int>> prev_pp;
- int prev_cnt = 0;
- int ans = 0;
- for (int i = 0; i < vi.size(); i++) {
- pair<int, pair<int, int>> pp = vi[i];
- if (vi[i].second.first == 1) {
- // end case
- assert(prev_cnt != 0);
- // if we have a more than 1 which ends at the same day
- // then prev_pp.first will be more than the last ended since we incremented last time
- // se below condition if (prev_cnt)
- if (prev_pp.first > pp.first) {
- prev_cnt--;
- prev_pp.second.second -= pp.second.second;
- continue;
- }
- int days = pp.first - prev_pp.first + 1;
- int cost = prev_pp.second.second;
- ans += min(C * days, prev_cnt * days * cost);
- prev_cnt--;
- if (prev_cnt) {
- prev_pp.first = pp.first + 1;
- prev_pp.second.second -= pp.second.second;
- }
- } else {
- // start case
- if (prev_cnt == 0) {
- prev_pp = vi[i];
- prev_cnt++;
- continue;
- }
- int days = pp.first - prev_pp.first;
- int cost = prev_pp.second.second;
- ans += min(C * days, prev_cnt * days * cost);
- prev_cnt++;
- prev_pp.first = pp.first;
- prev_pp.second.second += pp.second.second;
- }
- }
- assert(prev_cnt == 0);
- return ans;
- }
- int32_t main()
- {
- ios::sync_with_stdio(false);
- #ifndef ONLINE_JUDGE
- srand(time(NULL));
- #endif
- int T = 1;
- //cin >> T;
- for (int t = 1; t <= T; t++) {
- int ans = _solve();
- cout << ans << endl;
- //cout << "Case #" << t << ": " << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement