1
class Solution {
2
 public:
3
  int splitArray(vector<int> &nums, int m) {
4
    long long low = 0;
5
    long long res = 0;
6
    long long high = 1000000005;
7
    while (low <= high) {
8
      long long mid = (low + high) / 2;
9
      int cnt = 1;
10
      long long current_sum = 0;
11
      int can = 1;
12
      for (auto num : nums) {
13
        if (num > mid) {
14
          can = 0;
15
          break;
16
        }
17
        if (current_sum + num > mid) {
18
          cnt++;
19
          current_sum = 0;
20
        }
21
        current_sum += num;
22
      }
23
      if (can == 1) {
24
        if (cnt > m) {
25
          low = mid + 1;
26
        } else {
27
          res = mid;
28
          high = mid - 1;
29
        }
30
      } else {
31
        low = mid + 1;
32
      }
33
    }
34
    return res;
35
  }
36
};