josiftepe

Untitled

Oct 17th, 2020
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <sstream>
  7. #include <cstdio>
  8. #include <algorithm>
  9. #include <stack>
  10. #include <queue>
  11. #include <cmath>
  12. #include <iomanip>
  13. #include <fstream>
  14. using namespace std;
  15.  
  16. int main() {
  17.     ios_base::sync_with_stdio(false);
  18.     int n;
  19.     cin>>n;
  20.     int prof=0;
  21.     vector <int>a(n);
  22.     for (int i=0;i<n;i++){
  23.         cin>> a[i];
  24.     }
  25.     sort (a.begin(),a.end());
  26.     int b[n],c[n];
  27.     vector<pair<int, int> > v;
  28.     for (int i=0;i<n;i++){
  29.         cin>>b[i];
  30.         cin>>c[i];
  31.         v.push_back(make_pair (c[i],b[i]));
  32.     }
  33.     sort (v.begin(),v.end());
  34.     cout << endl;
  35.     for (int i=n-1;i>=0;i--){
  36.         int left_bound = 0;
  37.         int right_bound = (int) a.size() - 1;
  38.         int it = -1;
  39.         while(left_bound <= right_bound) {
  40.             int middle = (left_bound + right_bound) / 2;
  41.             if(a[middle] > v[i].second) {
  42.                 right_bound = middle - 1;
  43.             }
  44.             else {
  45.                 left_bound = middle + 1;
  46.                 it = middle;
  47.             }
  48.         }
  49.         if(it != -1) {
  50.             a.erase(a.begin() + it);
  51.             prof += v[i].first;
  52.         }
  53.        
  54.        
  55.     }
  56.  
  57.  
  58.  
  59.  
  60. cout<<prof << endl;
  61. }
  62. // 412137702
  63. // 412137702
  64.  
Advertisement
Add Comment
Please, Sign In to add comment