fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7.  
  8. int main() {
  9.     int n;
  10. 	cin >> n;
  11.  
  12.  
  13.     vector<ll> req(n);
  14.     vector<ll> stock(n);
  15.     vector<ll> cost(n);
  16.     ll budget;
  17.  
  18.     for (int i = 0; i < n; i++) {
  19.         cin >> req[i];
  20.     }
  21.  
  22.     for (int i = 0; i < n; i++) {
  23.         cin >> stock[i];
  24.     }
  25.  
  26.     for (int i = 0; i < n; i++) {
  27.         cin >> cost[i];
  28.     }
  29.  
  30.     // Total budget
  31.     cin >> budget;
  32.  
  33. 	ll low = 0;
  34. 	ll high = 1e8;
  35. 	ll answer = 0;
  36.  
  37.     // Binary search to find maximum possible items 'i'
  38.     while (low < high) {
  39.     	ll mid = (low + high) / 2;
  40.         ll sum = 0;
  41.  
  42.         for (int j = 0; j < n; j++) {
  43.             ll req_amount = req[j] * mid;
  44.             ll need = req_amount - stock[j];
  45.  
  46.             if (need > 0) {
  47.                 sum += need * cost[j];
  48.             }
  49.         }
  50.  
  51.         if (sum <= budget) {
  52. 			answer = mid;
  53. 			low = mid + 1;
  54.         } else {
  55.              high = mid - 1; // Budget exceeded
  56.         }
  57.     }
  58.  
  59.     cout << "Answer: " << answer << "\n";
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
2
1
2
0
1
1
1
3
stdout
copy 
Answer: 1
https://ideone.com/U2bFFF
language:
C++ (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!