fork download
copy 
  1. /*
  2. Problem: Maximize total value from using tools
  3.  
  4. You have n tools. Tool i can be used a[i] times.
  5. Each time you use a tool, its value decreases:
  6. - First use gives a[i] points
  7. - Second use gives a[i]-1 points
  8. - Third use gives a[i]-2 points
  9. - ... and so on down to 1 point
  10.  
  11. You can make exactly m total uses across all tools.
  12. Find the maximum total points you can get.
  13.  
  14. Example:
  15. Tools: [5, 3]  (tool 1 can be used 5 times, tool 2 can be used 3 times)
  16. If m = 4 uses allowed:
  17.  
  18. Best strategy: Take the highest value uses
  19. - Use tool 1 once: get 5 points
  20. - Use tool 2 once: get 3 points  
  21. - Use tool 1 again: get 4 points
  22. - Use tool 2 again: get 2 points
  23. Total = 5 + 3 + 4 + 2 = 14 points
  24.  
  25. ==================================================================================
  26. HOW WE SOLVE THIS:
  27. ==================================================================================
  28.  
  29. The greedy approach: Always pick the highest value use available.
  30.  
  31. But checking all possible uses one by one would be too slow for large inputs.
  32.  
  33. BETTER IDEA: Use binary search!
  34.  
  35. Key insight: If we decide on a "cutoff value" T, we can quickly calculate:
  36. "How many uses give value >= T?"
  37.  
  38. For a tool with max value x:
  39. - If T <= x, it has uses worth x, x-1, x-2, ..., T
  40. - That's (x - T + 1) uses with value >= T
  41.  
  42. Once we know the cutoff T:
  43. 1. Take ALL uses with value > T (these are the best)
  44. 2. Fill up remaining uses with value exactly T
  45.  
  46. How to find the right cutoff T?
  47. - Binary search! 
  48. - We want the HIGHEST value T where there are at least m uses with value >= T
  49. - This ensures we take the best m uses possible
  50.  
  51. Example walkthrough:
  52. Tools: [5, 3], m = 4
  53.  
  54. Try T = 4:
  55. - Tool 1 (value 5): has uses worth 5, 4 → that's 2 uses
  56. - Tool 2 (value 3): value 3 < 4 → no uses
  57. - Total: 2 uses with value >= 4
  58. - Is 2 >= 4? No, so T = 4 is too high
  59.  
  60. Try T = 2:
  61. - Tool 1 (value 5): has uses worth 5, 4, 3, 2 → that's 4 uses  
  62. - Tool 2 (value 3): has uses worth 3, 2 → that's 2 uses
  63. - Total: 6 uses with value >= 2
  64. - Is 6 >= 4? Yes! So T = 2 works
  65.  
  66. Try T = 3:
  67. - Tool 1 (value 5): has uses worth 5, 4, 3 → that's 3 uses
  68. - Tool 2 (value 3): has uses worth 3 → that's 1 use  
  69. - Total: 4 uses with value >= 3
  70. - Is 4 >= 4? Yes! T = 3 is even better!
  71.  
  72. So the answer with cutoff T = 3:
  73. - Take all values > 3: from tool 1 get (5 + 4) = 9 points (2 uses)
  74. - Need 2 more uses with value = 3: get 3 + 3 = 6 points
  75. - Total: 9 + 6 = 15 points
  76.  
  77. Special case: If m > total available uses, just use everything!
  78.  
  79. Time complexity: O(n log(max_value)) - binary search × counting
  80. Space complexity: O(n) for storing the tools
  81. ==================================================================================
  82. */
  83.  
  84. #include <bits/stdc++.h>
  85. using namespace std;
  86.  
  87. int main(){
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.  
  91.     int n;  // number of tools
  92.     long long m;  // number of uses we're allowed to make
  93.     cin >> n >> m;
  94.  
  95.     vector<long long> tool(n);  // tool[i] = max value of tool i
  96.     long long max_tool_value = 0;
  97.     __int128 total_uses_available = 0;
  98.  
  99.     for(int i = 0; i < n; i++){
  100.         cin >> tool[i];
  101.         if(tool[i] > max_tool_value) {
  102.             max_tool_value = tool[i];
  103.         }
  104.         total_uses_available += tool[i];
  105.     }
  106.  
  107.     // Special case: if we can use more than what's available, just take everything
  108.     if((__int128)m > total_uses_available){
  109.         __int128 answer = 0;
  110.         for(long long value : tool){
  111.             // Sum of 1 + 2 + ... + value = value * (value + 1) / 2
  112.             answer += (__int128)value * (value + 1) / 2;
  113.         }
  114.  
  115.         // Print the 128-bit result
  116.         if(answer == 0){ 
  117.             cout << 0 << "\n"; 
  118.         } else {
  119.             string output;
  120.             __int128 temp = answer;
  121.             while(temp > 0){
  122.                 output.push_back('0' + (temp % 10));
  123.                 temp /= 10;
  124.             }
  125.             reverse(output.begin(), output.end());
  126.             cout << output << "\n";
  127.         }
  128.         return 0;
  129.     }
  130.  
  131.     // Function: count how many uses have value >= threshold
  132.     auto count_high_value_uses = [&](long long threshold) -> __int128 {
  133.         __int128 total = 0;
  134.         for(long long value : tool){
  135.             // Tool with max value has uses: value, value-1, value-2, ..., 1
  136.             // How many are >= threshold? 
  137.             // That's value, value-1, ..., threshold which is (value - threshold + 1) uses
  138.             if(value >= threshold) {
  139.                 total += (value - threshold + 1);
  140.             }
  141.         }
  142.         return total;
  143.     };
  144.  
  145.     // Binary search to find the highest threshold where we have at least m uses
  146.     long long low = 1, high = max_tool_value;
  147.     long long threshold = 1;
  148.  
  149.     while(low <= high){
  150.         long long middle = low + (high - low) / 2;
  151.  
  152.         // Can we get at least m uses with value >= middle?
  153.         if(count_high_value_uses(middle) >= (__int128)m){
  154.             threshold = middle;  // Yes! Try a higher threshold
  155.             low = middle + 1;
  156.         } else {
  157.             high = middle - 1;    // No, threshold is too high
  158.         }
  159.     }
  160.  
  161.     // Now calculate the total value using this threshold
  162.     __int128 answer = 0;
  163.     __int128 uses_so_far = 0;
  164.  
  165.     // Step 1: Take all uses with value STRICTLY GREATER than the threshold
  166.     for(long long value : tool){
  167.         if(value > threshold){
  168.             // Take values: value, value-1, ..., (threshold + 1)
  169.             long long count = value - threshold;
  170.             uses_so_far += count;
  171.  
  172.             // Sum of arithmetic sequence: (first + last) * count / 2
  173.             // first = value, last = threshold + 1
  174.             answer += (__int128)(value + (threshold + 1)) * count / 2;
  175.         }
  176.     }
  177.  
  178.     // Step 2: Fill remaining uses with value exactly equal to the threshold
  179.     long long uses_left = (long long)((__int128)m - uses_so_far);
  180.     answer += (__int128)uses_left * threshold;
  181.  
  182.     // Print the 128-bit result
  183.     if(answer == 0){ 
  184.         cout << 0 << "\n"; 
  185.         return 0;
  186.     }
  187.  
  188.     string output;
  189.     __int128 temp = answer;
  190.     while(temp > 0){
  191.         output.push_back('0' + (temp % 10));
  192.         temp /= 10;
  193.     }
  194.     reverse(output.begin(), output.end());
  195.     cout << output << "\n";
  196.  
  197.     return 0;
  198. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/wOPsvs
language:
C++14 (gcc 8.3)
created:
2 days 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!