Advertisement
EWTD

Untitled

Mar 25th, 2020
512
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <bitset>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <map>
  7. using namespace std;
  8.  
  9. int main() {
  10.     int n;
  11.     cin >> n;
  12.     vector<pair<int,int>> vec;
  13.     vec.reserve(n);
  14.     int maxx = 0;
  15.     for(int i =0 ;i  < n; ++i){
  16.         int time, value;
  17.         cin >> time >> value;
  18.         maxx = max(time,maxx);
  19.         vec.push_back({time,value});
  20.     }
  21.     sort(vec.begin(),vec.end(),[&](const pair<int,int>& a, const pair<int,int>& b){
  22.         if (a.first == b.first){
  23.             return a.second > b.second;
  24.         }else{
  25.             return a.first < b.first;
  26.         }
  27.     });
  28.     long long ans = 0;
  29.     vector<int> ansv(maxx+1,0);
  30.     for(int i = 1 ; i <= maxx; ++i){
  31.         auto it = lower_bound(vec.begin(),vec.end(),i,[&](const pair<int,int>& a, int b){
  32.             return a.first < b;
  33.         });
  34.         if(it != vec.end()) {
  35.             ansv[i] =it->second;
  36.             vec.erase(it);
  37.         }
  38.     }
  39.     for(int i = 0; i < vec.size(); ++i){
  40.         int l = 1, r = vec[i].first;
  41.         int minn_index = -1, minn = 1000000000;
  42.         for(;l < r+1; ++l){
  43.             if(ansv[l] < minn){
  44.                 minn = ansv[l];
  45.                 minn_index =l;
  46.             }
  47.         }
  48.         if(minn < vec[i].second){
  49.             ansv[minn_index] = vec[i].second;
  50.         }
  51.     }
  52.     for(auto it: ansv){
  53.         ans += it;
  54.     }
  55.     cout << ans << '\n';
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement