1
class Solution {
2
 public:
3
  int waysToSplit(vector<int> &nums) {
4
    int n = nums.size(), mod = 1e9 + 7;
5
    long long ans = 0;
6
    vector<int> prefix(n);
7
    partial_sum(nums.begin(), nums.end(), prefix.begin());
8
    for (int i = 0; i < n - 2; i++) {
9
      int left = prefix[i], remain = (prefix[n - 1] - prefix[i]);
10
      if (remain < left * 2) break;
11
      int leftPtr =
12
          lower_bound(prefix.begin() + i + 1, prefix.end() - 1, left * 2) - prefix.begin();
13
      int rightPtr = upper_bound(prefix.begin() + i + 1, prefix.end() - 1, left + remain / 2) -
14
                     prefix.begin() - 1;
15

16
      if (rightPtr - leftPtr + 1 > 0) ans += rightPtr - leftPtr + 1;
17
    }
18

19
    return ans % mod;
20
  }
21
};