fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. ll f(vector<ll>& pages, vector<ll>& threshold) {
  7.     int n = pages.size();
  8.     map<int, vector<ll>> mp;
  9.  
  10.     for (int i = 0; i < n; ++i) {
  11.         mp[threshold[i]].push_back(pages[i]);
  12.     }
  13.  
  14.     for (auto& [_, v] : mp) sort(v.begin(), v.end());
  15.  
  16.     ll ans = 0;
  17.     priority_queue<ll, vector<ll>, greater<ll>> picked_vals;
  18.     for (auto& [x, v] : mp) {
  19.         // always pick the best x - picked_vals.size() vals from here
  20.         vector<ll> new_vals;
  21.         for (int i = 0; i < x - (int) picked_vals.size() && !v.empty(); ++i) {
  22.             new_vals.push_back(v.back());
  23.             v.pop_back();
  24.         }
  25.  
  26.         // can always replace an existing pick with a new val
  27.         while (!v.empty() && !picked_vals.empty() && v.back() > picked_vals.top()) {
  28.             ans += v.back() - picked_vals.top();
  29.             picked_vals.pop();
  30.             picked_vals.push(v.back());
  31.             v.pop_back();
  32.         }
  33.  
  34.         for (ll val : new_vals) {
  35.             picked_vals.push(val);
  36.             ans += val;
  37.         }
  38.  
  39.     }
  40.  
  41.     return ans;
  42. }
  43.  
  44.  
  45. int main() {
  46.  
  47.     vector<ll> pages{1000, 0, 0, 0,10,20,15,5,2, 3, 10, 100};
  48.     vector<ll> threshold{3,3,3,3,2,2,2,2,1,1,1, 1};
  49.  
  50.     cout << f(pages, threshold);
  51.  
  52.     return 0;
  53. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1120
https://ideone.com/lKTRjS
language:
C++14 (gcc 8.3)
created:
20 hours 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!