fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. int main() {
  6. 	int n;
  7. 	cin>>n;
  8. 	vector<int>a(n),c(n);
  9.     for(int i = 0; i < n; i++){
  10.     cin >> a[i];
  11. }
  12.  
  13. for(int i = 0; i < n; i++){
  14.     cin >> c[i];
  15. }
  16.  
  17.     vector<pair<ll,ll>>b;
  18.  
  19.     for(int i = 0;i < n ;i++){
  20.       b.push_back({a[i],c[i]});  	
  21.     }
  22.     sort(b.begin(),b.end());
  23.  
  24.     ll ans = 0;
  25.     ll prev = -1;
  26.  
  27.     int i = 0;
  28.     while(i<b.size()){
  29.       int j = i;
  30.  
  31.       while(j<b.size() && b[j].first == b[i].first){
  32.       	j++;
  33.       }
  34.  
  35.        vector<ll> costs;
  36.  
  37.         for (int k = i; k < j; k++) {
  38.             costs.push_back(b[k].second);
  39.         }
  40.  
  41.         // Largest cost gets smallest increment
  42.         sort(costs.rbegin(), costs.rend());
  43.  
  44.         ll start = max(b[i].first,prev+1);
  45.  
  46.         for(int k = 0 ; k < (int)costs.size();k++){
  47.         	ll x = start + k;
  48.  
  49.         	ans += (x - b[i].first)*costs[k];
  50.         	prev = x;
  51.         }
  52.  
  53.         i = j;
  54.     	}
  55.  
  56.  
  57.     cout<<ans<<endl;
  58. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
1 2 2 4
10 200 22 23
stdout
copy 
22
https://ideone.com/qnW3dk
language:
C++ (gcc 8.3)
created:
2 days 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!