fork(4) download
copy 
  1. #include <algorithm>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. std::vector<int> compute_cumulative_sum(const std::vector<int>& v)
  6. {
  7.     std::vector<int> res(1);
  8.  
  9.     int sum = 0;
  10.     for(auto e : v) {
  11.         sum += e;
  12.         res.push_back(sum);
  13.     }
  14.     return res;
  15. }
  16.  
  17. int get_min_partition3_value(const std::vector<int>& v)
  18. {
  19.     const auto cumulative_sum = compute_cumulative_sum(v);
  20.     const auto ideal_part = cumulative_sum.back() / 3;
  21.  
  22.     auto it1 = std::upper_bound(cumulative_sum.begin(), cumulative_sum.end(), ideal_part);
  23.     auto it2 = std::lower_bound(cumulative_sum.begin(), cumulative_sum.end(), cumulative_sum.back() - ideal_part);
  24.  
  25.     if (it1 == cumulative_sum.end()) {
  26.         return 0;
  27.     }
  28.     auto part1 = *it1;
  29.     auto part2 = *it2 - *it1;
  30.     auto part3 = cumulative_sum.back() - *it2;
  31.     auto res = std::max({ part1, part2, part3 });
  32.  
  33.     if(it1 != begin(cumulative_sum)) {
  34.         --it1;
  35.         part1 = *it1;
  36.         part2 = *it2 - *it1;
  37.         part3 = cumulative_sum.back() - *it2;
  38.         res = std::min(res, std::max({ part1, part2, part3 }));
  39.         ++it1;
  40.     }
  41.  
  42.     if(std::next(it2, 1) != end(cumulative_sum)) {
  43.         ++it2;
  44.         part1 = *it1;
  45.         part2 = *it2 - *it1;
  46.         part3 = cumulative_sum.back() - *it2;
  47.         res = std::min(res, std::max({ part1, part2, part3 }));
  48.  
  49.         if(it1 != begin(cumulative_sum)) {
  50.             --it1;
  51.             part1 = *it1;
  52.             part2 = *it2 - *it1;
  53.             part3 = cumulative_sum.back() - *it2;
  54.         }
  55.     }
  56.     return res;
  57. }
  58.  
  59. int main()
  60. {
  61.     std::cout << get_min_partition3_value({}) << std::endl;
  62.     std::cout << get_min_partition3_value({ 1, 1, 1, 1, 1, 1 }) << std::endl;
  63.     std::cout << get_min_partition3_value({ 2, 80, 50, 42, 1, 1, 1, 2 }) << std::endl;
  64.     std::cout << get_min_partition3_value({ 2, 5, 80, 1, 200, 80, 8000, 90 }) << std::endl;
  65.  
  66. }
  67.  
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
2
82
8000
https://ideone.com/rg3vST
language:
C++14 (gcc 8.3)
created:
9 years 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!