fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. long long findClosestSumWithinCapacity(int n, const vector<long long>& requirements, long long processingCapacity) {
  9.     int n1 = n / 2;
  10.     int n2 = n - n1;
  11.  
  12.     vector<long long> sums1;
  13.     for (int i = 0; i < (1 << n1); ++i) {
  14.         long long current_sum = 0;
  15.         for (int j = 0; j < n1; ++j) {
  16.             if ((i >> j) & 1) {
  17.                 current_sum += requirements[j];
  18.             }
  19.         }
  20.         sums1.push_back(current_sum);
  21.     }
  22.  
  23.     vector<long long> sums2;
  24.     for (int i = 0; i < (1 << n2); ++i) {
  25.         long long current_sum = 0;
  26.         for (int j = 0; j < n2; ++j) {
  27.             if ((i >> j) & 1) {
  28.                 current_sum += requirements[n1 + j];
  29.             }
  30.         }
  31.         sums2.push_back(current_sum);
  32.     }
  33.  
  34.     sort(sums2.begin(), sums2.end());
  35.  
  36.     long long maxAchievable = 0;
  37.  
  38.     for (long long s1 : sums1) {
  39.         long long remainingCapacity = processingCapacity - s1;
  40.         if (remainingCapacity >= 0) {
  41.             auto it = upper_bound(sums2.begin(), sums2.end(), remainingCapacity);
  42.             if (it == sums2.begin()) {
  43.                 if (s1 <= processingCapacity) {
  44.                     maxAchievable = max(maxAchievable, s1);
  45.                 }
  46.             } else {
  47.                 maxAchievable = max(maxAchievable, s1 + *(--it));
  48.             }
  49.         } else {
  50.             // If s1 itself is <= processingCapacity, consider it.
  51.             if (s1 <= processingCapacity) {
  52.                 maxAchievable = max(maxAchievable, s1);
  53.             }
  54.         }
  55.     }
  56.  
  57.     // Also consider sums only from the second half
  58.     for (long long s2 : sums2) {
  59.         if (s2 <= processingCapacity) {
  60.             maxAchievable = max(maxAchievable, s2);
  61.         }
  62.     }
  63.  
  64.     return maxAchievable;
  65. }
  66.  
  67. int main() {
  68.     int n;
  69.     cin >> n;
  70.  
  71.     vector<long long> requirements(n);
  72.     for (int i = 0; i < n; ++i) {
  73.         cin >> requirements[i];
  74.     }
  75.  
  76.     long long processingCapacity;
  77.     cin >> processingCapacity;
  78.  
  79.     long long result = findClosestSumWithinCapacity(n, requirements, processingCapacity);
  80.     cout << result << endl;
  81.  
  82.     return 0;
  83. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
600000000
700000000
800000000
900000000
1000000000
500000000
stdout
copy 
0
https://ideone.com/fpSNha
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!