fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. map<int, long long> generateCostBreakpoints(
  5.     const vector<int>& stock,
  6.     const vector<int>& require,
  7.     const vector<int>& cost,
  8.     int n)
  9. {
  10.     int m = stock.size();
  11.     map<int, long long> breakpoints;
  12.  
  13.     breakpoints[0] = 0; // start at 0 products with 0 cost
  14.  
  15.     // Priority queue for breakpoints when stock of item i runs out
  16.     struct Event {
  17.         int productCount;
  18.         long long extraCostPerProduct;
  19.         bool operator>(const Event& other) const {
  20.             return productCount > other.productCount;
  21.         }
  22.     };
  23.  
  24.     priority_queue<Event, vector<Event>, greater<Event>> pq;
  25.  
  26.     for (int i = 0; i < m; i++) {
  27.         if (require[i] == 0) continue;
  28.         int canCover = stock[i] / require[i];
  29.         if (canCover < n) {
  30.             long long extra = 1LL * require[i] * cost[i];
  31.             pq.push({canCover + 1, extra});
  32.         }
  33.     }
  34.  
  35.     long long currCost = 0;
  36.     long long slope = 0; // cost per product
  37.     int lastProd = 0;
  38.  
  39.     while (!pq.empty()) {
  40.         auto ev = pq.top(); pq.pop();
  41.         int prod = ev.productCount;
  42.  
  43.         if (prod > n) break;
  44.  
  45.         // Accumulate cost till this breakpoint
  46.         currCost += slope * (prod - lastProd);
  47.         breakpoints[prod] = currCost;
  48.  
  49.         // Increase slope after this breakpoint
  50.         slope += ev.extraCostPerProduct;
  51.         lastProd = prod;
  52.     }
  53.  
  54.     // Fill till n if needed
  55.     if (lastProd < n) {
  56.         currCost += slope * (n - lastProd);
  57.         breakpoints[n] = currCost;
  58.     }
  59.  
  60.     return breakpoints;
  61. }
  62.  
  63. int main() {
  64.     vector<int> stock = {10, 4};
  65.     vector<int> require = {2, 1};
  66.     vector<int> cost = {3, 5};
  67.     int n = 10;
  68.  
  69.     auto bp = generateCostBreakpoints(stock, require, cost, n);
  70.     for (auto& [prod, c] : bp) {
  71.         cout << prod << " -> " << c << "\n";
  72.     }
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 -> 0
5 -> 0
6 -> 5
10 -> 49
https://ideone.com/VswQoz
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!