fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(NULL);
  7.  
  8.     int t;
  9.     cin >> t;
  10.  
  11.     while (t--) {
  12.         int n, k;
  13.         cin >> n >> k;
  14.  
  15.         vector<pair<int, int>> customers(n);
  16.         vector<int> all_prices;
  17.  
  18.         for (int i = 0; i < n; i++) {
  19.             cin >> customers[i].first;
  20.         }
  21.         for (int i = 0; i < n; i++) {
  22.             cin >> customers[i].second;
  23.         }
  24.  
  25.         for (int i = 0; i < n; i++) {
  26.             all_prices.push_back(customers[i].first);
  27.             all_prices.push_back(customers[i].second);
  28.         }
  29.  
  30.         sort(all_prices.begin(), all_prices.end());
  31.         all_prices.erase(unique(all_prices.begin(), all_prices.end()), all_prices.end());
  32.  
  33.         long long max_revenue = 0;
  34.  
  35.         for (int p : all_prices) {
  36.             long long revenue = 0;
  37.             priority_queue<int, vector<int>, greater<int>> negative_reviews;
  38.  
  39.             for (const auto& customer : customers) {
  40.                 if (p <= customer.first) {
  41.                     // Positive reviewer
  42.                     revenue += p;
  43.                 } else if (p <= customer.second) {
  44.                     // Negative reviewer
  45.                     revenue += p;
  46.                     negative_reviews.push(p);
  47.  
  48.                     if (negative_reviews.size() > k) {
  49.                         revenue -= negative_reviews.top();
  50.                         negative_reviews.pop();
  51.                     }
  52.                 }
  53.             }
  54.  
  55.             max_revenue = max(max_revenue, revenue);
  56.         }
  57.  
  58.         cout << max_revenue << "\n";
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
5
2 0
2 1
3 4
1 1
2
5
3 3
1 5 2
3 6 4
4 3
2 3 2 8
3 7 3 9
3 1
2 9 5
12 14 9
stdout
copy 
2
5
9
14
18
https://ideone.com/h6rUay
language:
C++14 (clang 8.0)
created:
10 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!