rharjani

Untitled

Jan 18th, 2021
722
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //https://atcoder.jp/contests/abc188/tasks/abc188_d
  2.  
  3. #include <bits/stdc++.h>
  4. #include <time.h>
  5.  
  6. using namespace std;
  7.  
  8. #define int long long
  9. /*
  10. #define inp_file
  11. #define op_file
  12. */
  13.  
  14. int _solve()
  15. {
  16.     /*
  17.     #ifndef ONLINE_JUDGE
  18.     freopen(inp_file, "r", stdin);
  19.     freopen(op_file, "w", stdout);
  20.     #endif
  21.     */
  22.  
  23.     int N, C;
  24.     cin >> N >> C;
  25.     vector<pair<int, pair<int, int> > > vi;
  26.     for (int i = 0;i < N; i++) {
  27.         int st, en, c;
  28.         cin >> st >> en >> c;
  29.         vi.push_back({st, {0, c}});
  30.         vi.push_back({en, {1, c}});
  31.     }
  32.  
  33.     sort(vi.begin(), vi.end());
  34.  
  35.     pair<int, pair<int, int>> prev_pp;
  36.     int prev_cnt = 0;
  37.     int ans = 0;
  38.     for (int i = 0; i < vi.size(); i++) {
  39.         pair<int, pair<int, int>> pp = vi[i];
  40.  
  41.         if (vi[i].second.first == 1) {
  42.             // end case
  43.             assert(prev_cnt != 0);
  44.             // if we have a more than 1 which ends at the same day
  45.             // then prev_pp.first will be more than the last ended since we incremented last time
  46.             // se below condition if (prev_cnt)
  47.             if (prev_pp.first > pp.first) {
  48.                 prev_cnt--;
  49.                 prev_pp.second.second -= pp.second.second;
  50.                 continue;
  51.             }
  52.             int days = pp.first - prev_pp.first + 1;
  53.             int cost = prev_pp.second.second;
  54.             ans += min(C * days, prev_cnt * days * cost);
  55.             prev_cnt--;
  56.             if (prev_cnt) {
  57.                 prev_pp.first = pp.first + 1;
  58.                 prev_pp.second.second -= pp.second.second;
  59.             }
  60.         } else {
  61.             // start case
  62.             if (prev_cnt == 0) {
  63.                 prev_pp = vi[i];
  64.                 prev_cnt++;
  65.                 continue;
  66.             }
  67.             int days = pp.first - prev_pp.first;
  68.             int cost = prev_pp.second.second;
  69.             ans += min(C * days, prev_cnt * days * cost);
  70.             prev_cnt++;
  71.             prev_pp.first = pp.first;
  72.             prev_pp.second.second += pp.second.second;
  73.         }
  74.     }
  75.     assert(prev_cnt == 0);
  76.  
  77.     return ans;
  78. }
  79.  
  80. int32_t main()
  81. {
  82.     ios::sync_with_stdio(false);
  83.     #ifndef ONLINE_JUDGE
  84.     srand(time(NULL));
  85.     #endif
  86.  
  87.     int T = 1;
  88.     //cin >> T;
  89.     for (int t = 1; t <= T; t++) {
  90.      int ans = _solve();
  91.      cout << ans << endl;
  92.      //cout << "Case #" << t << ": " << ans << endl;
  93.     }
  94.     return 0;
  95. }
RAW Paste Data