subtask 1:

đầu tiên, chúng ta phải thử xây dựng 1 hàm, kiểm tra xem từ ~n~ món hàng có thể chia ra ~k~ nhóm hàng có giá trị là tối đa là ~val~ hay không

ll cal(ll val){
    ll segs=1;// tính số đoạn đã chia được 
    ll s=0;// tính tổng của từng đoạn con 
    for(int i=0;i<n;i++){
        if(a[i]>val){
            return k+1;// trường hợp a[i] lớn hơn val thì max của mảng không nằm ở đây nữa, có thể return số lớn hơn k và trở về ngay
        }
        if(s+a[i]<=val){
            s+=a[i];
        }
        else s=a[i],segs++;
    }

    return segs;
    // nếu số đoạn tính được từ n món hàng
}

với cách kiểm tra trên, mỗi lần kiểm tra ta tốn dpt là o(n), n=10^5

dễ nhận thấy đây là hàm nghiêm nghặt tăng theo giá trị val -> có thể áp dụng chặt nhị phân

subtask 2:

ta chặt nhị phân tìm cận dưới của hàm cal, ta không thể duyệt thử tất cả trường hợp với val từ 1->10^18 vì giá trị vì giá trị của ~cal~ có thể rất lớn. vì sẽ có tận 10^18 trường hợp thử, nhân với dpt với mỗi lần thử, ta có được dpt là 10^5*10^18 = 10^23 -> quá mức tính toán của máy chấm trong 1s. máy chấm chỉ tính được khoảng 10^8 phép tính / giây -> cần tốn khoảng 30 triệu năm để tính toán xong dược.

nếu áp dụng chặt nhị phân ta giảm xuống dpt còn n * log2(10^18) = 60n -> phù hợp với yêu cầu của bài toán.

ll bs_lower_bound() {
    ll l = 0;
    ll h = 1e18;
    while (l < h) {
        ll mid =  l + (h - l) / 2;
        if (cal(mid)<=k) {
            h = mid;
        } else {
            l = mid + 1;


        }
    }
    return l;
}