fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. long long findMaximumAlloyUnits(vector<int> composition,
  7.                                vector<int> stock,
  8.                                vector<int> cost,
  9.                                int budget) {
  10.  
  11.     int n = composition.size();
  12.  
  13.     ll low = 0, high = 1000000000LL;
  14.     ll ans = 0;
  15.  
  16.     while (low <= high) {
  17.         ll mid = low + (high - low) / 2;
  18.  
  19.         ll sum = 0;
  20.  
  21.         for (int i = 0; i < n; i++) {
  22.  
  23.             ll need = 1LL * composition[i] * mid;
  24.             ll extra = max(0LL, need - stock[i]);
  25.  
  26.             sum += extra * cost[i];
  27.  
  28.             if (sum > budget)
  29.                 break;
  30.         }
  31.  
  32.         if (sum <= budget) {
  33.             ans = mid;
  34.             low = mid + 1;
  35.         } else {
  36.             high = mid - 1;
  37.         }
  38.     }
  39.  
  40.     return ans;
  41. }
  42.  
  43. int main() {
  44.  
  45.     int n;
  46.     cin >> n;
  47.  
  48.     vector<int> composition(n), stock(n), cost(n);
  49.  
  50.     for (int i = 0; i < n; i++)
  51.         cin >> composition[i];
  52.  
  53.     for (int i = 0; i < n; i++)
  54.         cin >> stock[i];
  55.  
  56.     for (int i = 0; i < n; i++)
  57.         cin >> cost[i];
  58.  
  59.     int budget;
  60.     cin >> budget;
  61.  
  62.     cout << findMaximumAlloyUnits(composition, stock, cost, budget);
  63.  
  64.     return 0;
  65. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
1 2
0 1
1 1
3
stdout
copy 
1
https://ideone.com/i2ptPm
language:
C++ (gcc 8.3)
created:
4 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!