Advertisement
Guest User

Untitled

a guest
Feb 29th, 2020
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. constexpr int MAX_N {200005};
  6.  
  7. int main()
  8. {
  9.     ios::sync_with_stdio(false);
  10.     int n;
  11.     cin >> n;
  12.     vector<int> a(n);
  13.     map<int, int> f;
  14.     for (int i = 0; i < n; ++i) { cin >> a[i]; f[a[i]]++; }
  15.     vector<pair<int, int>> b(n);
  16.     for (int i = 0; i < n; ++i)
  17.     {
  18.         int t;
  19.         cin >> t;
  20.         b[i] = {t, a[i]};
  21.     }
  22.     sort(begin(b), end(b));
  23.  
  24.     set<int> available_nums;
  25.     for (int i = 1; i <= 2 * MAX_N; ++i) { available_nums.insert(i); }
  26.  
  27.     bitset<MAX_N> processed;
  28.  
  29.     long long ans = 0;
  30.     for (int i = 0; i < n; ++i)
  31.     {
  32.         int t, num;
  33.         tie(t, num) = b[i];
  34.  
  35.         if (f[num] > 1) { continue; }
  36.  
  37.         auto it = available_nums.lower_bound(num);
  38.         ans += (*it - num) * (long long) t;
  39.         available_nums.erase(it);
  40.         processed[i] = true;
  41.     }
  42.  
  43.     for (int i = n - 1; i >= 0; --i)
  44.     {
  45.         if (processed[i]) { continue; }
  46.  
  47.         int t, num;
  48.         tie(t, num) = b[i];
  49.         auto it = available_nums.lower_bound(num);
  50.         ans += (*it - num) * (long long) t;
  51.         available_nums.erase(it);
  52.     }
  53.  
  54.     cout << ans << endl;
  55.  
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement