fork(1) download
copy 
  1. #include <algorithm>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. unsigned int get_min_partition3_value(const std::vector<unsigned int>& v)
  6. {
  7.     const unsigned int total_sum = std::accumulate(v.begin(), v.end(), 0u);
  8.     auto it1 = v.begin();
  9.     auto it2 = v.end();
  10.     unsigned int part1 = 0;
  11.     unsigned int part2 = total_sum;
  12.     unsigned int part3 = 0;
  13.     unsigned int res = part2;
  14.  
  15.     while (part1 < part2 && part3 < part2) {
  16.         res = part2; // part2 is greater than part1&part2
  17.         if (part1 + *it1 < part3 + *(it2 - 1)) {
  18.             part1 += *it1;
  19.             part2 -= *it1;
  20.             ++it1;
  21.         } else {
  22.             --it2;
  23.             part3 += *it2;
  24.             part2 -= *it2;
  25.         }
  26.     }
  27.     res = std::min(res, std::max(part1, part3));
  28.     return res;
  29. }
  30.  
  31. int main()
  32. {
  33.     std::cout << get_min_partition3_value({}) << std::endl; // 0
  34.     std::cout << get_min_partition3_value({ 1, 1, 1, 1, 1, 1 }) << std::endl; // 2
  35.     std::cout << get_min_partition3_value({ 2, 80, 50, 42, 1, 1, 1, 2 }) << std::endl; // 82
  36.     std::cout << get_min_partition3_value({ 2, 5, 80, 1, 200, 80, 8000, 90 }) << std::endl; // 8000
  37.     std::cout << get_min_partition3_value({5, 6, 1, 4, 9, 3, 1, 2}) << std::endl; // 13
  38. }
  39.  
Success #stdin #stdout 0s 3272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
2
82
8000
13
https://ideone.com/Hwo1xh
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!