fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void executeTime() {
  5.     cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " secs";
  6. }
  7.  
  8. using ll = long long;
  9.  
  10. int main() {
  11.  
  12.     int n; cin >> n;
  13.  
  14.     vector<array<int, 2>> v(n);
  15.     for (auto &x : v) {
  16.         cin >> x[0];
  17.     }
  18.  
  19.     for (auto &x : v) {
  20.         cin >> x[1];
  21.     }
  22.  
  23.     sort(v.begin(), v.end());
  24.  
  25.     priority_queue<array<int, 2>> pq;
  26.  
  27.     ll sum = 0, ans = 0;
  28.  
  29.     int curr = v[0][0];
  30.  
  31.     int i = 0;
  32.  
  33.     while (i < n) {
  34.  
  35.         while (i < n && v[i][0] == curr) {
  36.             pq.push({v[i][1], v[i][0]});
  37.             sum += v[i][1];
  38.             i++;
  39.         }
  40.  
  41.         if (pq.empty()) {
  42.             curr = v[i][0];
  43.             continue;
  44.         }
  45.  
  46.         int c = pq.top()[0];
  47.         pq.pop();
  48.  
  49.         sum -= c;
  50.         ans += sum;
  51.         curr++;
  52.     }
  53.  
  54.     while (!pq.empty()) {
  55.         int c = pq.top()[0];
  56.         sum -= c;
  57.  
  58.         pq.pop();
  59.  
  60.         ans += sum;
  61.     }
  62.  
  63.     cout << ans << endl;
  64.  
  65.     executeTime();
  66.     return 0;
  67. }
Success #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
5
1 1 5 5 10
10 3 8 2 20
stdout
copy 
5
stderr
copy 
Time Taken: 0.004315 secs
https://ideone.com/q7VvW1
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!