#include <vector>
using namespace std;
class Solution{
public: // 410. O(log(R-L+1) * n), O(1)
    int splitArray(vector<int>& a, int k){
        const int n = (int)a.size();
        int L = 0, R = 0;
        for (int i = 0; i < n; ++i){
            if(a[i] > L) L = a[i];
            R += a[i];
        }
        auto ok = [&](int c){
            int need = 1, cur = 0;
            for(int i = 0; i < n; ++i){
                if(cur + a[i] > c){
                    if(++need > k) return false;
                    cur = a[i];
                } else {
                    cur += a[i];
                }
            }
            return true;
        };
        while (L < R){
            int m = L + (R - L) / 2;
            if (ok(m)) R = m;
            else L = m + 1;
        }
        return L;
    }
};